Sum Of Square Numbers Problem
Description
LeetCode Problem 633.
Given a non-negative integer c, decide whether there’re two integers a and b such that a^2 + b^2 = c.
Example 1:
1
2
3
Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
1
2
Input: c = 3
Output: false
Example 3:
1
2
Input: c = 4
Output: true
Example 4:
1
2
Input: c = 2
Output: true
Example 5:
1
2
Input: c = 1
Output: true
Constraints:
- 0 <= c <= 2^31 - 1
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool judgeSquareSum(int c) {
if (c < 0)
return false;
long int left = 0, right = sqrt(c);
while (left <= right) {
long int cur = left * left + right * right;
if (cur < c)
left ++;
else if (cur > c)
right --;
else
return true;
}
return false;
}
};