Hackerrank - Project Euler+ #014 - Longest Collatz sequence

Hackerrank - Problem description

The problem description - Hackerrank.

Solution

There are given 2 rules for Collatz sequence:

  • if n is even, then n/2
  • if n is odd, then 3n + 1

The given problem set of possibilities is to big and it would take too much time.

My solution is to precalculate sequence values of 1 to 5 000 000 and then to store them into a cache to reuse them.

Let's start with starting values.

For 1 there is a size of Collatz sequence 1 unit.

2: I use the rule and divide it by 2, because it is even. The sequence would by 2 long - The result of division is 1. I look into the cache and I see that I have calculated the size of the sequence with starting value as 1 is 1.

3 similar: There is nothing in the cache for 3. I need to multiply and increment 1. The result is 10 (actual sequence size is 1). 10 is not in the cache, I need to divide. The result is 5 (the sequence size is already 2). 5 is not in the cache, I need to multiply and the result is 16 (the sequence size is 3). 16 is not in the cache and I need to divide by 2 with the result 8 (size of the sequence is 4). 8 is not in the cache, I need to divide with the result 4 (size is 5). 4 is not in the cache, divide by 2, result is 2 (size is 6). 2 is present in the cache and its size is 2. I sum the sizes 6 + 2.
It means that the size of Collatz sequence for the number 3 is 8.

4: It is not in the cache, divide by 2 with the result 2 (actual size of the sequence is 1). 2 is in the cache with the length value 2. The complete size of the Collatz sequence is 1 + 2 = 3.

etc.

I need to remember the longest Collatz sequence:

  • 1: from 1 to 1 is the longest sequence 1 unit
  • 2: from 1 to 2 is the longest sequence 2 (1 has the sequence 1 unit long)
  • 3: from 1 to 3 is the longest sequence 8
  • 4: from 1 to 4 is the longest sequence 8 (1 has 1, 2 has 2, 3 has 8 and 4 has 3)

I created solution in:

All solutions are also available on my GitHub profile.

Java

Leave a Reply