## 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | import java.util.Scanner; public class LongestCollatzSequence { private static final int CACHE_SIZE = 5_000_000; // stores collatz sequence for number at index private static int[] cache = new int[CACHE_SIZE + 1]; // stores number with max collatz sequence at index private static int[] collatzCache = new int[CACHE_SIZE + 1]; public static void main(String[] args) { precomputeCache(); Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { int n = Integer.parseInt(scanner.nextLine()); System.out.println(collatzCache[n]); } scanner.close(); } private static void precomputeCache() { cache[0] = 1; cache[1] = 1; collatzCache[0] = 1; collatzCache[1] = 1; int maxSeq = 0; int maxNum = 0; for (int j = 2; j <= CACHE_SIZE; j++) { int collatzSeq = 0; long number = j; while (number > 1) { if(cache[j] > 0) { collatzSeq += cache[j]; break; } collatzSeq++; if(number % 2 == 0) { number >>= 1; } else { number = 3 * number + 1; } } cache[j] = collatzSeq; if(collatzSeq >= maxSeq) { maxSeq = collatzSeq; maxNum = j; } collatzCache[j] = maxNum; } } } |