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)
1import math
2
3def judgeSquareSum(c):
4 a = 0
5 b = int(math.sqrt(c))
6 while a <= b:
7 sum = a * a + b * b
8 if sum == c:
9 return True
10 elif sum < c:
11 a += 1
12 else:
13 b -= 1
14 return FalsePython's implementation uses math.sqrt and an iterative check using the two-pointer technique.
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.