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)
1using System;
2
3public class Solution {
4 public bool JudgeSquareSum(int c) {
5 int a = 0;
6 int b = (int)Math.Sqrt(c);
7 while (a <= b) {
8 int sum = a * a + b * b;
9 if (sum == c) {
10 return true;
11 } else if (sum < c) {
12 a++;
13 } else {
14 b--;
15 }
16 }
17 return false;
18 }
19}C# uses Math.Sqrt for the calculation and follows the same logic path as other implementations.
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
bool isPerfectSquare(int num) {
int sq = static_cast<int>(std::sqrt(num));
return sq * sq == num;
}
bool judgeSquareSum(int c) {
for (int a = 0; a * a <= c; a++) {
if (isPerfectSquare(c - a * a)) {
return true;
}
}
return false;
}Similar to the C approach, but utilizing C++ syntax within a function to check if a number is a perfect square.