## Double Square Problem Analysis

January 10, 2011

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 = 32 + 12. 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 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.

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.

Here is my problem analysis for Facebook Hacker Cup Qualification Round: Double Square. While you are reading the problems, you would notice a little subtitle under the main title “Facebook Hacker Cup” that says “Too hard for brute force, switching to dp“. It’s there for a purpose.

Double Square Problem Analysis:
This problem can be brute-forced (Read below for an efficient O(vM) solution). At first I thought of an approach using DP, but it would require an array of size 2147483647, which requires at least 2GB of memory (assuming each element of the array is of type unsigned char).

Some interesting double squares. Isn’t Math beautiful?

Unfortunately, my C++ program failed to allocate such huge amount of memory. I quickly thought of another approach using bit manipulation to store two values in each array element (ie, each occupying 4 bits, half of the size of unsigned char). Although this halved the memory usage requirement, this also means the maximum value of each element could not exceed 24 = 16, which is not true, since the largest value could go up to 64. (ie, total number of double squares for the number 1215306625 is 64.)

The brute-force method is easy to implement and its complexity is O(M), where M is the input number. Since the input specified that N (total number of inputs) is at most 100, the brute force approach still holds, even though it might take about 30 seconds to few minutes to run.

Update:

Thanks to a reader Pingvin, who suggested an efficient O(vM) solution!

Consider that:
M = x2 + y2,

and we have y2 = Mx2.

We can easily tell if (M - x2) 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!

VN:F [1.9.22_1171]
Double Square Problem Analysis, 3.5 out of 5 based on 2 ratings

### 26 responses to Double Square Problem Analysis

1. Would you really need an array of size 2147483647 though? Wouldn't it suffice to just populate the array with squares of numbers from 1 to approximately sqrt(2^31 – 1), which is 46 340?

VA:F [1.9.22_1171]
0
2. @ajay:
Your solution is just saving the time of re-computing the square of numbers. However, if I feed the same input to your function 1000 times, you are still re-computing the same thing over and over again.

In fact, the brute force solution is in the same complexity O(M) as your solution, and plus it does not require the extra memory space.

Tell me how can you avoid unnecessary re-computations without not using array of size 2147483647.

VA:F [1.9.22_1171]
0
3. Yes, you're absolutely right, the complexity is the same as the brute force solution. All I was saying though, was that you don't need an array of that size. Here's what I'd do – compute squares of 1…46340, and store them in a hash table of that size. Then, for some number N, traverse the array for index i = 1 .. N/2, and look in the hashtable to see if N – A[i] is in it, if so, we've found a solution.

VA:F [1.9.22_1171]
0
4. You can make it in O(sqrt M) very easily.

Considering that if you have M = x^2 + y^2 and you know M and x^2, y can be found by sqrt(M – x^2).
Testing is it natural number trunc(y) == y will provide if-clause.

VA:F [1.9.22_1171]
0
5. Brute forcing this problem is better suited to a linked list. But Pingvin's solution trumps them both.
start pointers at first and last nodes and run until first == last

ex.
while (FirstNode != LastNode)
{
tmp = FirstNode.Value + LastNode.Value;
if (tmp == i)
ret++;
if (tmp > i)
LastNode = LastNode.Previous;
else
FirstNode = FirstNode.Next;
}
The linked list being the squares from 0 to floor(sqrt(X))

VA:F [1.9.22_1171]
0
6. @Pingvin:
Wow! Your method is definitely very elegant and it attacks this problem right to the point!

I have updated my post with your solution. Thanks!

VA:F [1.9.22_1171]
0
7. I didn't use sqrt function because of the rounding error it can make.

Instead of doing so, we can use a STL set for the square number from 0 to max. It has less element than 50000.
Then in the code we just have to examine totally sqrt(m/2) case in this way:
you can iterate in square numbers stored from 0 to m/2 (it is [sqrt(m/2)]+1 different number) let it be named x.
All you have to check in every case is weather m-x is or not in the square number set
this checking's complexity is O(logn)
where n is the number of the stored square numbers which is less than 50000.
log2(5000) is approximately 16
so the numbers of computations needed by one case is O(sqrt(m/2)) plus above all you have to do constant 50000 computation to calculate square number first and put it into the set.

I think this solution eliminates the errors may be derived from using sqrt function and also avoid multiple calculations of the same square numbers.

VA:F [1.9.22_1171]
0
8. Here is my solution in C#. O(sqrt N)

public static int NumberOfDoubleSquares(int n)
{
int[] numbers;
int sqrt_n = (int) Math.Sqrt(n);
numbers = new int[sqrt_n+1];
for(int i=0; i<= sqrt_n; i++)
numbers[i] = i;

int count = 0;
for(int i=0; i<=sqrt_n; i++)
{
if (numbers[i] < 0)
continue;
int remainder = n – i * i;
int x = (int)Math.Sqrt(remainder);
if (x * x == remainder)
{
numbers[i] = -1; numbers[x] = -1;
count++;
}
}
return count;
}

VA:F [1.9.22_1171]
0
9. Jacobi's Two Square Theorem can be applied to this problem. The theorem provides a simple method to find the number of ways in which a positive integer can be written as a sum of two squares.

Jacobi's Two Square Theorem: The number of representations of a positive integer as a sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4.

Note that the number of representations does not ignore order and signs. If n=a^2+b^2 then
n = a^2 + b^2
= (-a)^2+b^2
= a^2 + (-b)^2
= b^2 + a^2
= (-b)^2 + a^2
= b^2 + (-a)^2
= (-b)^2 + (-a)^2
= (-a)^2 + (-b)^2 .
So, we will divide the number of representations by eight.

Jacobi's Two Square Theorem (Modified): The number of representations (ignoring sign and order) of a positive integer as a sum of two squares is equal to half of the the difference of the numbers of divisors congruent to 1 and 3 modulo 4.

VA:F [1.9.22_1171]
0
10. Dude, can't you use 3^2 and 1^2 instead of 32 and 12? Confused the heck out of me.

VA:F [1.9.22_1171]
0
11. @Anonymous:
Sorry, fixed!

VA:F [1.9.22_1171]
0
12. great work

VA:F [1.9.22_1171]
0
13. Hi,

Can you please explain me, why are you dividing m by 2 before taking sqrt.
p = sqrt((double)m / 2.0)

VA:F [1.9.22_1171]
0
• Suppose a^2 + b^2 = X; and a>=b, you have
a^2+b^2 =X>=2a^2
=> a<=sqrt(x/2.0)
So, the loop upper bound issqrt((double)m / 2.0)

VN:F [1.9.22_1171]
0
14. Hi 1337coder,

I think this problem is very similar to the classic problem: find two numbers in a sorted array which sum up to a given value.

In this problem, we first obtain the upper bound by sqrt(X), then follow the same way to scan from both sides. complexity is O(sqrt).

cnt = 0;
i = 1, j = sqrt(X);
while (i X)
j–;
else if (sum < X)
i++;
else /* sum == X */
cnt++;
}

VA:F [1.9.22_1171]
0
15. Simplest (I guess O(sqrt n)) solution would be, floor(sqrt(number))/2 – 1

VA:F [1.9.22_1171]
0
16. >>> # A Simple Solution in python
… import math

… def check(i):
… if i==int(i):
… return 1
… else :
… return 0

… def doublesquare(N):
… c=0
… a=math.sqrt(N)
… if check(a):
… c=-1
… a=int(a)
… for i in range(0,a):
… temp =math.sqrt(N-i*i)
… c+= check(temp)

… if temp*temp >>

VA:F [1.9.22_1171]
0
• # A Simple Solution in python
import math
def check(i):
if i==int(i):
return 1
else :
return 0
def doublesquare(N):
c=0
a=math.sqrt(N)
if check(a):
c=-1
a=int(a)
for i in range(0,a):
temp =math.sqrt(N-i*i)
c+= check(temp)
if temp*temp < i*i:
break
print c
# use method doublesquare
li = [25,5,10,1215306625]
for i in li:
doublesquare(i)

VA:F [1.9.22_1171]
0
17. Actually in the search if we go from larger to smaller number instead of from smaller to larger number, the computational cost is reduced by half, as every time reducing a large number means we jump through a huge amount of small number

VN:F [1.9.22_1171]
0
18. In your algorithmic analysis you should include the time complexity of finding square root. For your original problem this is not an issue because you don’t need the exact square root for the value of iUpper. You can instead find the largest number whose square is less than or equal to m. This will be O(m).

But since Pingvin’s program requires exact square root which requires to at least look into the time complexity of the algorithm used in sqrt.

VN:F [1.9.22_1171]
0
19. void double_square(int x){
// Searhc in a matrix of i rows and j cols. Value of element(i, j) is (i*i + j*j). O(sqrt(x))
int i, j, n, s;
n = (int)sqrt(x);
for(i = n, j = 0; i >= j;){
s = i*i + j*j;
if(x > s)
j += 1;
if(x < s)
i -= 1;
if(x == s){
printf("%d, %d\n", i, j);
i -= 1;
j += 1;
}
}
}

VN:F [1.9.22_1171]
0
20. The precision issue in the second approach can be avoided using equation (don’t use any double expect for finding upper limit of loop),

M + 2*X*Y = (X + Y)^2

Any values of X and Y that satisfy above can be solution set.

Also, the input M can be rejected if M %4 results 3. No number can be expressed as sum of two squares if the number modulo 4 results 3.

VN:F [1.9.22_1171]
0
• @ Venki, I think your approach is good with given X, Y and M. However, Y is unknown. The step, Y=sqrt(m-X^2), avoids searching for all possible values for Y.

VA:F [1.9.22_1171]
0
21. precision issue can be eliminated if we don’t use sqrt(x)， but use binary search to check if x is square, this would be an O(mlogm) method, still fast enough

VN:F [1.9.22_1171]
0
22. however, the sqrt function is NOT a O(1) … actually it is O( log N ) , i don’t know why most people ignore that, even-though the log factor is too small we must consider it anyway.

VN:F [1.9.22_1171]
0