Click Here for Problem Statement
How do I do This ? ?
Solve each testcase separately :
There are at most sqrt(n) squares to check.
So iterate through integers 1…sqrt(n).
Let this integer be x. Now we just want to check if n-x*x is square too.
If it is return true.
If over iterating through this integers you haven’t found the squares return false.
It is clear that it runs in O(sqrt(n)).
You can speed it a little bit by omiting symmetrical cases and iterating only to floor(sqrt(n/2)).
Any number (lets say A) can be represented in form 4k+r (where r can 0 , 1 , 2 , 3). Thus possible values for A^2 is 4k and 4*k+1 .
so sum of two squares can never be of the form 4*k +3 .
N = p1 ^ x1 * p2 ^ x2 * …… pm ^ xm (prime factorisation of N) can be represented as the sum of two squares if every prime of the form 4*k +3 have even degree (or power) .
This can be proved using following 5 statements :-
The product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.
If a number which is a sum of two squares is divisible by a prime which is a sum of two squares, then the quotient is a sum of two squares.
If a number which can be written as a sum of two squares is divisible by a number which is not a sum of two squares, then the quotient has a factor which is not a sum of two squares.
If a and b are relatively prime then every factor of a^2 + b^2 is a sum of two squares.
Every prime of the form 4n+1 is a sum of two squares.