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:

Java

All solutions are also available on my GitHub profile.

Java

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;
        }
    }
}

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;

}

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Project Euler+ #014 – Longest Collatz sequence

Hackerrank – Problem description

Solution

Java

Leave a Reply Cancel reply