Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.
Solution
To solve this problem, we can use a two-pointer approach. The idea is to initialize two pointers, a and b, where a starts from 0 and b starts from the square root of c.
Upper Bound: For any non-negative integer c, the largest possible value for a or b such that a2+b2=c is square root of c. This is because if both a and b were greater than square root of c then their sum of squares would exceed c.
Then:
- Calculate the sum of squares: sum = a^2 + b^2.
- If sum is equal to c, return true.
- If sum is less than c, increment a.
- If sum is greater than c, decrement b.
- Repeat steps 1-4 until a is greater than b.
public bool JudgeSquareSum(int c) {
long a = 0;
long b = (long)Math.Sqrt(c);
while (a <= b) {
long sum = a * a + b * b;
if (sum == c) {
return true;
} else if (sum < c) {
a++;
} else
b--;
}
}
return false;
}