CODEWITHSUNDEEP
javarecursioncollatz
monsterbananas
monsterbananas

Reputation: 41

Project Euler 14 Java

I have been having trouble on Problem 14 on Project Euler. I don't understand why my code(Java) isn't working and any help would be appreciated.

public class Calculate {

    public static void main(String[] args){
        System.out.println(calc());
    }

    public static int calc(){
        int max = 0;
        int maxI = 0;
        for (int i = 0; i < 1000000; i++){
            if (seqLen(i) >= max){
                max = seqLen(i);
                maxI = i;
            }
        }
        return maxI;
    }

    public static int seqLen(int seed){
        if (seed <= 0) return 0;
        if (seed == 1) return 1;
        int len = 1;
        if (seed % 2 == 0){
            len += seqLen(seed/2);
        }
        else{
            len += seqLen((3*seed)+1);
        }
        return len;
    }

}

Thanks!

Upvotes: 3

Views: 430

Answers (3)

Soonil Hong
Soonil Hong

Reputation: 27

Actually, you don't have to check from 1 to 499999. You only need to check from 500000 to 999999 because the next step of any even number between 500000 and 999999 is going to be some integer from 1 to 499999. That means that an integer from 1 to 499999 cannot be the answer.

So change the for loop to the following

for (int i = 500000; i < 1000000; i++) {

}

And "i" doesn't have to be long while "seed" has to be long.

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65851

You are breaking the int limit.

Using long:

public static long calc() {
    long max = 0;
    long maxI = 0;
    for (long i = 0; i < 1000000; i++) {
        long len = seqLen(i);
        if (len >= max) {
            max = len;
            maxI = i;
        }
    }
    return maxI;
}

public static long seqLen(long seed) {
    if (seed <= 0) {
        return 0;
    }
    if (seed == 1) {
        return 1;
    }
    long len = 1;
    if (seed % 2 == 0) {
        len += seqLen(seed / 2);
    } else {
        len += seqLen((3 * seed) + 1);
    }
    return len;
}

public void test() {
    System.out.println(seqLen(13));
    System.out.println(calc());
}

Gives you the correct result of 837799.

Note that there are better/more efficient algorithms than this one.

Upvotes: 1

Sirko
Sirko

Reputation: 74076

You run into an overflow with your int variables.

The maximum number appearing in this computation (when using a brute force approach) is 56991483520.

Java's int maximum value is 2^31-1 == 2147483647, which is obviously smaller.

So change your variables etc to use long. Here the max value is 2^63-1 == 9223372036854775807, which will be fitting for all values.

Upvotes: 2

Related Questions