JANUARY 11, 2011
Double Squares is the 1st (and the easiest) of the 3 problems posted in the qualification round for the 2011 Facebook Hacker Cup. It consists of calculating how many combinations of adding two squared [integer] numbers equal a given number.
Here’s a copy of the problem description:
Double Squares
A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don’t count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.
Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100
Output
For each value of X, you should output the number of ways to write X as the sum of two squares.
Example input
21
326864818
874566596
1816371419
77068225
1991891221
65
326122507
1041493518
4005625
29641625
3
1257431873
602519112
5928325
25
2147483642
2147483646
415485223
372654318
160225
2147483647
Example output
0
1
0
36
1
2
0
0
20
32
0
0
4
24
2
0
0
0
0
12
0
Overall the problem is fairly easy, I solved it using a dynamic programming algorithm in which I make an array with all the squares smaller than the largest possible number and then create two pointers to it, one starting at 0 and the other at the square root of the number to search. I move either of those pointers depending on whether the sum of them is lesser, greater or equal (where I also update a counter) to the number given. This solution is O(n), which is considered very fast.
I initially squandered my opportunity to submit this by (unknowingly) opening the input file before coding the solution. After Facebook decided to allow resubmission, I did so and my solution was accepted.
Anyway, here’s the source code I made:
import java.util.Scanner;
/**
* @author Luis Edgardo Argote Bolio
* This solution is O(n)
*/
public class Main {
public static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
// This gets the maximum number that can be squared
long limit = 2147483647;
int maxNumber = (int) Math.sqrt(limit) + 1;
long[] squares = new long[maxNumber];
// Calculates the squares for all the relevant numbers < maxNumber
// There is no point in exploring other possibilities
// This is done once at program startup
for (int i = 0; i < maxNumber; i++) {
squares[i] = i * i;
}
int inputs = in.nextInt();
for (int i = 0; i < inputs; i++) {
long number = in.nextInt();
// Set the lower pointer at zero to consider all squares from 0
int pos1 = 0;
// Set the higher pointer at sqrt(number) to consider all squares up
// to number
int pos2 = (int) Math.sqrt(number);
int count = 0;
while (pos1 <= pos2) {
if (squares[pos1] + squares[pos2] > number) {
// If the sum is lower than the number, increase the right
// (higher) number pointer
pos2--;
} else if (squares[pos1] + squares[pos2] < number) {
// If the sum is lower than the number, increase the left
// (lower) number pointer
pos1++;
} else {
// Increase the match count
count++;
// No point in reusing the same numbers as moving only one
// pointer will cause the sum to be different from the number
pos1++;
pos2--;
}
}
System.out.println(count);
}
}
}