Hacker Cup - Double Squares - Solution
At the end of my last post, I mentioned I was going to run my code against the sample set to see if it works and then try out the worst-case dataset.
Well, it worked well against the sample and simply would not complete in the worst case because of my crappy non-algorithm. Let’s think about what I was doing wrong.
My approach was to try and sum the squares of every combination of numbers less than the input number.
And ya know what? It works perfectly well for a low order input like 25, but it IS a very dumb, brute-force sort of algorithm.
Now try this approach on a number like 2147483647, which just so happens to be the upper constraint specified by Facebook.
You can’t do it.
That’s 2147483647! or 2147483647 factorial.
In order to compute a solution for this, we’d need the lifespan of many more universes than the one we have. Such a task would require a far, far greater number of universes than even the total number of atoms in this universe! Yeah.
Fortunately, there are a number of tricks we can use to lower the difficulty.
We know right away that many of those numbers in our combinations list aren’t even necessary because their sum will be greater than the input.
So, we can set a limit on which numbers we’ll square and sum by dividing the input in half, and taking the square root:
limit = sqrt(input/2)
Already, this reduces our 2147483647! to 32768!, which is still an incomputably large number if we’re calculating for every possible combination of integers in this smaller set.
Stop it. We don’t need to do that.
Instead, we’ll just iterate through the list, and for each number n, we’ll do this:
sqrt(input - (n * n))
If the resultant square root evaluates to an integer (i.e., not a decimal), then we know that we have a match.
This vastly improved algorithm runs the worst case (2147483647 x 100) in 108 milliseconds under Java.
No further optimization necessary and problem solved. Here’s a peek at the actual code that does the work:
int[] sumArr = app.readSumsFromFile(args[0]);
List<Integer> resultsList = new ArrayList<Integer>();
for(int sum : sumArr) {
int matches = 0;
double theLimit = Math.sqrt(sum/2);
// This next check handles the sum^2 + 0^2 case
if(Math.sqrt(sum)%1==0) {
matches++;
}
for(int i=1;i<=theLimit;i++) {
if(Math.sqrt((sum-(i*i)))%1==0)
matches++;
}
resultsList.add(new Integer(matches));
}
}
