Sponsored
Sponsored
The first approach involves using the two-pointer technique. Given an integer c, you start with two pointers a initialized at 0 and b initialized at the square root of c. You calculate a^2 + b^2 and compare it with c. If it equals c, return true. If the sum is less than c, increment a to increase the sum. If the sum is greater than c, decrement b to decrease the sum. Continue this until a exceeds b.
Time Complexity: O(sqrt(c))
Space Complexity: O(1)
1function judgeSquareSum(c) {
2 let a = 0;
3 let b = Math.floor(Math.sqrt(c));
4 while (a <= b) {
5 const sum = a * a + b * b;
6 if (sum === c) {
7 return true;
8 } else if (sum < c) {
9 a++;
10 } else {
11 b--;
12 }
13 }
14 return false;
15}JavaScript's implementation relies on Math.sqrt and uses an iterative method to find if the sum of two squares equals c.
This approach is a brute-force method. Start with a single loop iterating from a = 0 to sqrt(c). For each value of a, calculate a^2 and check if c - a^2 is a perfect square. If it is, return true, otherwise continue. If the loop completes without finding such values, return false.
Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check.
Space Complexity: O(1)
1
public class Solution {
private bool IsPerfectSquare(int num) {
int sq = (int)Math.Sqrt(num);
return sq * sq == num;
}
public bool JudgeSquareSum(int c) {
for (int a = 0; a * a <= c; a++) {
if (IsPerfectSquare(c - a * a)) {
return true;
}
}
return false;
}
}The C# function IsPerfectSquare checks if c - a^2 forms a perfect square for all a up to sqrt(c).