Sum of Square Numbers — Solution in Python, Java & C++
Sum of Square Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Square Numbers is a medium coding problem on math, binary search and two pointers, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Math, Binary Search, Two Pointers
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a non-negative integer c, decide whether there exist non-negative integers a and b with a² + b² == c.
Return true if such a pair exists.
Example 1
Input: c = 5
Output: true
Explanation: 1² + 2² = 5.
Example 2
Input: c = 3
Output: false
Example 3
Input: c = 4
Output: true
Explanation: 0² + 2² = 4.
Constraints
0 <= c <= 10000000
Hints for Sum of Square Numbers
Hint 1
Both squares are at most
c, soaandblie between 0 andfloor(sqrt(c)).Hint 2
Two pointers from the ends of that range work: the sum increases with
aand decreases withb.Hint 3
Compute the integer square root by a loop rather than a floating-point
sqrt.
How to solve Sum of Square Numbers
Search the pair (a, b) with a <= b <= sqrt(c) using two pointers. The sum a² + b² rises when a rises and falls when b falls, so every candidate is covered in one sweep.
Approach
- Find the largest
bwithb² <= cby an integer loop. - Start
aat 0 and comparea² + b²withc. - Increase
awhen the sum is too small; decreasebwhen it is too large; report success on equality. - Stop when the pointers cross.
Why it works
Any solution has a <= b after swapping, and both are at most sqrt(c). The sweep is monotone in both directions, so it neither skips a solution nor revisits a pair.
Complexity
- Time —
O(sqrt(c)) - Space —
O(1)
Pitfalls
- A floating-point
sqrtcan land one off on a perfect square, and the judge's C harness has nomath.h— the integer loop avoids both. aandbmay be zero, soc = 0andc = 4both answertrue.b * bstays inside 32 bits at this limit, but at LeetCode's real bound it needs a wider type.
Reference solution
Python
def judgeSquareSum(c: int) -> bool:
a, b = 0, 0
while (b + 1) * (b + 1) <= c:
b += 1
while a <= b:
total = a * a + b * b
if total == c:
return True
if total < c:
a += 1
else:
b -= 1
return FalseJava
public static boolean judgeSquareSum(int c) {
long a = 0, b = 0;
while ((b + 1) * (b + 1) <= c) b++;
while (a <= b) {
long sum = a * a + b * b;
if (sum == c) return true;
if (sum < c) a++;
else b--;
}
return false;
}C++
bool judgeSquareSum(int c) {
long long a = 0, b = 0;
while ((b + 1) * (b + 1) <= c) b++;
while (a <= b) {
long long sum = a * a + b * b;
if (sum == c) return true;
if (sum < c) a++;
else b--;
}
return false;
}JavaScript
var judgeSquareSum = function(c) {
var a = 0, b = 0;
while ((b + 1) * (b + 1) <= c) b++;
while (a <= b) {
var sum = a * a + b * b;
if (sum === c) return true;
if (sum < c) a++;
else b--;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search · Two Pointers Technique