Sum of Square Numbers
Problem
Given a non-negative integer c, return true if and only if there exist non-negative integers a, b such that a² + b² = c.
c = 5truedef judge_square_sum(c):
lo, hi = 0, int(c ** 0.5)
while lo <= hi:
s = lo * lo + hi * hi
if s == c:
return True
elif s < c:
lo += 1
else:
hi -= 1
return Falsefunction judgeSquareSum(c) {
let lo = 0, hi = Math.floor(Math.sqrt(c));
while (lo <= hi) {
const s = lo * lo + hi * hi;
if (s === c) return true;
else if (s < c) lo++;
else hi--;
}
return false;
}class Solution {
public boolean judgeSquareSum(int c) {
long lo = 0, hi = (long) Math.sqrt(c);
while (lo <= hi) {
long s = lo * lo + hi * hi;
if (s == c) return true;
else if (s < c) lo++;
else hi--;
}
return false;
}
}bool judgeSquareSum(int c) {
long lo = 0, hi = (long) sqrt((double) c);
while (lo <= hi) {
long s = lo * lo + hi * hi;
if (s == c) return true;
else if (s < c) lo++;
else hi--;
}
return false;
}Explanation
We want two whole numbers a and b with a² + b² = c. Instead of testing every pair, we use two pointers that squeeze toward each other, which is much faster.
The smallest possible candidate is lo = 0, and the largest useful one is hi = ⌊√c⌋ — anything bigger than that already squares past c by itself. So the answer, if it exists, must use values inside the range [lo, hi].
At each step we compute s = lo*lo + hi*hi. If s == c we found it and return true. If s is too small, we raise lo to add value; if it is too big, we lower hi to remove value. Each move discards numbers that can never help.
Example: c = 5, so hi = 2. Start with 0² + 2² = 4 < 5, so lo++. Now 1² + 2² = 5, which equals c, so the answer is true.
The pointers only move inward and never cross back, so the loop runs about √c times — quick even for large c.