Thursday, December 18, 2014

Number of ways to represent an integer as sum of two squares

Given a number, we have to find out the number ways to express it in the form of sum of two integer squares.

For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)

24 cannot be written as a sum of any two squares.

Mathematically this problem is to find the roots of the equation x2+y2-n = 0 where n is given.

The algorithm for this problem is simple. let us start i with 0 and check if (n-i*i) is a perfect square. We repeat this process until (n-i*i) is greater than i*i

Take the example of 25, Here is the trace of the algorithm

i          n-i*i      Result
0          25        - Yes
1          24        - No
2          21        - No
3          16        - Yes
4          9         - break

Here is the C++ code to do this.