# Python, Straightforward with Explanation

• ``````def judgeSquareSum(self, c):
def is_square(N):
return int(N**.5)**2 == N

return any(is_square(c - a*a)
for a in xrange(int(c**.5) + 1))
``````

Without loss of generality, let's consider only `a, b >= 0`. This is because if say, `a < 0`, then we may also find a solution using `abs(a)`.

Now, `a*a = c - b*b <= c`, because `b*b >= 0`, and `0 <= a <= sqrt(c)` is a necessary condition for a solution.

Let's try each `0 <= a <= sqrt(c)`. For each choice of `a`, we must have `b*b = c - a*a`. There will be a solution if and only if the right-hand-side is a perfect square.

• `a` can be further constrained by `a*a <= c/2`. If there is no solution in this range for `a`, then there cannot be a solution when `c/2 < a*a <= c`.
Proof: if there is one solution with `a * a > c/2`, then the corresponding `b` must satisfy `b * b <= c/2`. Consequently, the solution `(b, a)` should have already been found.

``````#include <cmath>
class Solution {
public:
bool judgeSquareSum(int c) {
auto end = (int)std::sqrt(c / 2.0);
for (int a = 0; a <= end; a++){
auto bs = c - a * a; // b^2
auto b = (int)std::sqrt(bs);
if (b * b == bs)
return true;
}
return false;
}
};``````

• This post is deleted!

• @HongxiangWang `1*1 + 1*1 = 2`

• @awice Oh, thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.