Algorithmic Programming with C III

Facebook Hacker Cup (Qualification Round / Q1)

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*3 + 1*1. 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*3 + 1*1 (we don’t count 1*1 + 3*3 as being different). On the other hand, 25 can be written as 5*5 + 0*0 or as 4*4 + 3*3.

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:

5
10
25
3
0
1

Example Output:

1
2
0
1
1

Analysis

This problem was taken from the qualification round of the Facebook Hacker Cup 2010. Basically, this problem itself does not require any special knowledge nor any advanced programming technique to get to a solution. It’s rather simple and can be solved even by brute force taking time complexity only of O(N) * O(X) which is already good enough.

Here is one with brute force that people could think of at the first glance:

1
2
3
4
5
6
7
8
9
10
11

int count_ss(long n){
    int count = 0;
    long max_x = (long) sqrt(n / 2);
    for (long x = 0; x <= max_x ; x++) {
        double y = sqrt(n - x * x);
        if (y == (long) y) {
            count++;
        }
    }
    return count;
}

It is quite short, simple, and comprehensible. Because this function will have to be called, presumably, upon large numbers, it could be improved a bit further by building up a static array of squares at the beginning in order to reduce the calculations. However, under timed environment, particularly on a machine with a low clock speed – every clock cycle is precious, multiplications for computing squares and square roots turn out to be evils. I thus look for an algorithm that can work even better than this version.

Here is my solution I found after spending a couple of hours on optimization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int count_ss(long n) {
    int count;
    long ss, x, y;
    count = ss = x = y = 0;
    if (n == 0) {
        return 1;
    }
    while(ss < n) {
        ss += 2 * x + 1;
        x++; 
    } 
    while (x >= y) {
        if (ss < n) { 
            ss += 2 * y + 1; 
            y++; 
        } else if (ss > n) {
            ss -= 2 * x - 1;
            x--;
        } else {
            count++;
            ss += 2 * (y - x + 1);
            y++;
            x--;
        }
    }
    return count;
}

Note that multiplications by two will be optimized further by the compiler by turning them into addition expressions or probably bit shifting. Therefore, the algorithm above will be totally multiplication-free after getting compiled.