Double Square Problem Analysis

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]
Rating: 3.6/5 (13 votes cast)
Double Square Problem Analysis, 3.6 out of 5 based on 13 ratings

40 thoughts on “Double Square Problem Analysis

  1. ajay

    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]
    +2
  2. 1337c0d3r

    @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. ajay

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

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

    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. 1337c0d3r

    @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. Anonymous

    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]
    +1
  8. Cygwin98

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

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

    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
  11. maxq

    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]
    +1
  12. Rahul

    >>> # 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
    1. Rahul

      # 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
  13. Sun Yi

    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]
    +1
  14. thequark

    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]
    +1
  15. liny

    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]
    +1
  16. Venki

    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
    1. Moussa

      @ 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
  17. Pingback: Programming Questions | ragwendra

  18. sabz

    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.

    VA:F [1.9.22_1171]
    0
    1. sabz

      Here is the scala code

      VA:F [1.9.22_1171]
      0
      1. sabz

        VA:F [1.9.22_1171]
        0
  19. sabz

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

    VA:F [1.9.22_1171]
    0
  20. Pingback: LeetCode | Technical interview solutions

  21. SeriMert

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

    VA:F [1.9.22_1171]
    0
    1. SeriMert

      Website didnt copy my code correctly so i post again

      VA:F [1.9.22_1171]
      0
      1. SeriMert

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

        VA:F [1.9.22_1171]
        0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*