Help Debugging Euler Problem 23 - JAVA

Jason Anello Thanks so much for the help. Generally, I've heard for project euler problems people try to keep it under a minute. With your correction I got the correct answer but it took 142 seconds. Any recomendations?

I think once your solution is accepted you gain access to a private forum where different solutions and algorithms can be discussed. I recommend that you read as much of that as you can because you'll learn far more than whatever I can tell you here.

I'm on a slower computer than you. It was 400 seconds for me but I was able to get it down to about 1.5 seconds. It might end up being less than a second for you.

One thing I forgot to mention before is that you should change your timing calculation to a floating point calculation so you don't lose the milliseconds. It doesn't matter much right now but when your times are faster it will be good to have.

System.out.println("Time: " + (endTime - startTime)/1000.0 + " seconds");

I don't know how much you know so hopefully I'm not explaining too much that you already know.

I ended up doing the optimizations in reverse order of effectiveness. The last one I did had the biggest improvement.

I started with isAbundant but its the final for loop checking the sums that takes up the majority of the time.

The contains method on an ArrayList operates in linear time. Meaning you have to look at every number in the array to know whether each number is in there. So you're checking 28,000 numbers against however many sums there are.

I don't know if you are familiar with big O notation and the running time of algorithms but here's a graph on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation#/media/File:Comparison_computational_complexity.svg

The green line represents linear time and the purple or pink line (labeled 1) at the bottom is constant time. You can see how much more quickly the linear line grows as compared to both the logarithmic and constant time. Either of those would be preferable over linear if given the choice.

By switching over to a HashSet you can search in constant time: https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

This class offers constant time performance for the basic operations (add, remove, contains and size), ...

Plus the added benefit of no duplicate sums.

HashSet<Integer> abundantSums = new HashSet<Integer>();

That should take out a huge chunk of the time.

Another thing you can do with the sums is not add them if they are greater than the MAX value. Although this likely won't have any affect since a HashMap is used.

if (temp <= MAX) {
    abundantSums.add(temp);
}

The only other thing that I thought of was the is_abundant method. You don't have to check for divisors all the way up to the number you're checking. You only have to go up to the square root of the number. This really cuts down on the number of mod operations you have to perform.

Divisors come in pairs, like 2 and 12 are divisor pairs for 24. So if you know that 2 is a divisor then you can get the 12 by doing 24/2 You don't actually have to loop all the way up to the 12 and do a mod operation to see that it goes into 24 evenly.

public static boolean isAbundant(int n) {
        int sum = 1;
        int upper = (int) Math.sqrt(n);

        for (int i = 2; i <= upper; i++) {
            if (n % i == 0) {
                sum += i;
                if (i*i != n) {
                    sum += n/i;
                }
            }
        }

        if(sum > n) {
            return true;
        } else {
            return false;
        }
    }

Let me know if you have any questions.

Also, let me know what your time is, I'm curious.