A double-square number is an integer

Xwhich 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 32 + 12 (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 integerN, the number of test cases. The nextNlines will containNvalues ofX.

Constraints

0 =X= 2147483647

1 =N= 100

Output

For each value ofX, you should output the number of ways to writeXas 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*(v*M*) 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).

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 2^{4} = 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.

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

**Update:**Thanks to a reader **Pingvin**, who suggested an efficient *O*(v*M*) solution!

Consider that:*M* = *x*^{2} + *y*^{2},

and we have *y*^{2} = *M* – *x*^{2}.

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!

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

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?

+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.

0Yes, 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.

0You 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.

0http://programmingpraxis.com/2010/01/05/the-sum-of-two-squares/2/

+1Brute 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))

0@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!

0I 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.

+1Here 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;

}

0Jacobi'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.0Dude, can't you use 3^2 and 1^2 instead of 32 and 12? Confused the heck out of me. 😛

0@Anonymous:

Sorry, fixed!

0great work

0Hi,

Can you please explain me, why are you dividing m by 2 before taking sqrt.

p = sqrt((double)m / 2.0)

0Suppose 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)

-1Hi 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++;

}

+1Simplest (I guess O(sqrt n)) solution would be, floor(sqrt(number))/2 – 1

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

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

0Actually 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

+1In 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.

+1void 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;

}

}

}

+1The 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.

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.

0precision 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

0however, 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.

0Scan from sqrt(n/2) to sqrt(n) will be more efficient than 1 to sqrt(n/2) because sqrt(n/2) > sqrt(n)/2

+1You are right. We can get improvement by doing this.

0Pingback: Programming Questions | ragwendra

Using a little mathematics, we can further optimize Pingvin’s solution. An odd number can only be represented as the sum of squares of an odd number and an even number. An even number can be represented as either the sum of squares of two even numbers or two odd numbers. This knowledge can generally reduce the search for solutions by half. i.e., O(Sqrt(m)/2), compared to Pingvin’s O(Sqrt(m/2)). In the case of odd m, one can not assume x<y where x is an odd number. So the search spans all odd numbers in 1..Sqrt(m). In the case of even m, x and y must both be even or odd. One can then assume x<=y and search even or odd numbers up to Sqrt(m)/2.

0Here is the scala code

00Seems Leetcode does not parse scala code nicely. Here’s the plain text.

object DoubleSquare extends App {

val m = Int.MaxValue

val epsilon = 0.000000001

//when m is even

(0 to m by 2).foreach{ i=>

val limit = Math.sqrt(i/2).toInt

//O(sqrt(i/2)/2)

val evens = for (x<-0 to limit by 2; y=Math.sqrt(i-x*x); if (y-y.toInt)<epsilon) yield (i, x, y.toInt)

//O(sqrt(i/2)/2)

val odds = for (x<-1 to limit by 2; y=Math.sqrt(i-x*x); if (y-y.toInt)

val limit = Math.sqrt(i).toInt

//O(sqrt(i)/2)

val odds = for (x<-1 to limit by 2; y=Math.sqrt(i-x*x); if (y-y.toInt)<epsilon) yield (i, x, y.toInt)

odds.sorted.foreach(println)

}

}

0Pingback: LeetCode | Technical interview solutions

This is just a two sum problem. Generate an array of 0^2, 1^1, 2^2, 3^2,… (floor(M^0.5)+1)^2

0Solution code does not find all of it. I checked my code, it finds every possible and total recursive function call is ALWAYS lower than square root of the number.

0Website didnt copy my code correctly so i post again

0There is a problem with website that it does not show all the code this is why i will post without code snippet.

private static void findEquals(int n1, int n2)

{

worstCaseCheck++;

if(n1 > 0 && n2 < root )

{

if(addSquare(n1,n2) < num)

{

if(n1 < preciseHalfRoot && counter num)

{

counter++;

findEquals(n1-1,n2);

}

else

{

counter = 0;

System.out.println(num + ” is sum of squares.\n”

+ “Numbers are ” + n1 +” – “+ n2 + “\n”);

found = true;

findEquals(n1-1,n2+1);

}

}

}

0nevermind my code because it never shows my code completely.. if anyone is wondering, i can send them.

0