Problem
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: c = 3
Output: false
Constraints:
0 <= c <= 2^31 - 1
Solution (Java)
class Solution {
public boolean judgeSquareSum(int c) {
int right = (int) Math.sqrt(c);
int left = (int) Math.sqrt((double) c / 2);
for (int i = left; i <= right; i++) {
int j = (int) Math.sqrt(c - (double) (i * i));
if (i * i + j * j == c) {
return true;
}
}
return false;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).