Project Euler #14: Longest Collatz sequence

Sort by

recency

|

208 Discussions

|

  • + 1 comment

    Here is the Python version of the Java code below. It works in PyPy.

    def num_state(num):
        num_state = 0
        while num != 1:
            if num % 2 == 0:
                num //= 2
            else:
                num = 3 * num + 1
            num_state += 1
        return num_state
    
    # Read all input
    t = int(input())
    arr_input = [int(input()) for _ in range(t)]
    max_val = max(arr_input)
    
    # Precompute answers
    ans = [0] * (max_val + 1)
    max_state = 1
    steps = 1
    
    for j in range(1, max_val + 1):
        state = num_state(j)
        if state >= max_state:
            max_state = state
            steps = j
        ans[j] = steps
    
    # Output results
    for val in arr_input:
        print(ans[val])
    
    • + 1 comment

      This one can't possibly pass all test cases?

      • + 0 comments

        It works on PyPy3, not Python 3. I didn't read the end of his sentence and went straight for Python 3 to only find that the code failed 4 test cases with runtime error. When I read the end of his sentence, I realised I used PyPy3 and it 100% pass all test cases.

  • + 0 comments

    My solution in Python worked for most of the test cases. Thing is, it didn't work on 4 of the test cases, and it seems like it just wants some hyper-optimizations that would end up being memory inefficient and weird. Seems like a pretty unfair set of test cases tbh.

  • + 0 comments
    import java.util.Scanner;
    
    public class Solution {
        public static long numState(long num) {
            long numState = 0;
            while (num != 1) {
                if (num % 2 == 0) {
                    num /= 2;
                } else {
                    num = 3 * num + 1;
                }
                numState++;
            }
            return numState;
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int t = scanner.nextInt();
            int[] arrInput = new int[t];
            int max = 0;
            for (int i = 0; i < t; i++) {
                arrInput[i] = scanner.nextInt();
                if (arrInput[i] > max) {
                    max = arrInput[i];
                }
            }
            long[] ans = new long[max + 1];
            long maxState = 1;
            long steps = 1;
            for (long j = 1; j <= max; j++) {
                long numState = numState(j);
                if (numState >= maxState) {
                    maxState = numState;
                    steps = j;
                }
                ans[(int) j] = steps;
            }
            for (int j = 0; j < t; j++) {
                System.out.println(ans[arrInput[j]]);
            }
        }
    }
    
  • + 0 comments

    out put for 20 terms is 18 please change it

  • + 1 comment

    Am I the only one facing problem with this code.... Starting number with the longest Collatz sequence up to 20 is 18 but why is the compiler expecting the answaer to be 19? 18>9>28>14>7>22>11>34>17>52>26>13>40>20>10>5>16>8>4>2>1

    • + 0 comments

      Yeah, I was facing that issue too. What happens here is that, for both 18 and 19 the length is same. So store the value which occur later.

      For both 18 and 19 it is 21.

      So, when your code store for 18, then in the next iteration, store for 19. Use something like lenght >= max_length