Double Square Problem Analysis | LeetCode + Facebook Hacker Cup

Double Square Problem Analysis | LeetCode
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² + 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 32 + 12 (we don't count 1² + 3² as being different). On the other hand, 25 can be written as 5² + 0² or as 4² + 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.

X. Consider that:
M = x² + y²,

and we have y² = M – x².

We can easily tell if (M - x^2) is a perfect square by taking the square root of it and compare it to its truncated value (deleting its fractional part). If both are equal, then it must be a perfect square, or else it is not. This observation is so subtle that many will miss it, yet it just clicks in your head right when you see it! Wow!

http://www.nitinh.com/2011/01/facebook-hacker-cup-double-squares-problem-solution/

2 3 4 5 6 7 8 9 10

int doubleSquare(unsigned int m) {   int p = sqrt((double)m / 2.0);   int total = 0;   for (int i = 0; i <= p; i++) {     double j = sqrt((double)m - i*i);     if (j - (int)j == 0.0)   // might have precision issue,       total++;  // can be resolved using |j-(int)j| == delta   }   return total; }

Brute Force:
http://www.codeproject.com/Articles/568029/Facebook-Hacker-Cup-Double-Squares-Solution-in-Jav
https://jack.ofspades.com/facebook-hacker-cup-double-squares-problem-in-coffee/

2 3 4 5 6 7 8 9 10 11 12 13 14 15

int doubleSquare(unsigned int m) {   int total = 0;   int iUpper = sqrt((double)m / 2.0);   for (int i = 0; i <= iUpper; i++) {     unsigned int ii = i*i;     for (int j = i; ; j++) {       unsigned int sum = ii + j*j;       if (sum == m)         total++;       else if (sum > m)         break;     }   }   return total; }

Facebook Hacker Cup – Double Squares

  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);
        }
    }
}

Read full article from Double Square Problem Analysis | LeetCode