# O(nlogn) time and O(1) space binary search solution.

• The idea is to find a number b, which b^2 == c - a^2 . If b exists, return true. Otherwise return false. This question now becomes to judge if a number has an integer root.

Note that neither abs(a) or abs(b) should be greater than sqrt(c) , otherwise we just return false.

It's not neccessary to count negative integers in for a and b because (-2)^2 == (2)^2. We can just start from 0.

``````class Solution {
public:
bool judgeSquareSum(int c) {
int r = sqrt(c);
if (r * r == c)
{
return true;
}

for (int i = r; i >= 0; --i)
{
if (isSquarable(c - i * i))
{
return true;
}
}

return false;
}

private:
bool isSquarable(int c)
{
int r = sqrt(c);
if (r * r == c)
{
return true;
}

int b = 0;
int e = r;

while (b <= e)
{
int m = b + (e - b) / 2;

if (m * m == c)
{
return true;
}

if (m * m < c)
{
b = m + 1;
}
else
{
e = m - 1;
}
}

return false;
}
};
``````

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