Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: c = 5 Output: true Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: c = 3 Output: false
Constraints:
0 <= c <= 231 - 1The goal in #633 Sum of Square Numbers is to determine whether a non‑negative integer c can be expressed as the sum of squares of two integers: a² + b² = c. A practical way to reason about this problem is to limit the search space to values between 0 and sqrt(c), since any larger square would exceed c.
A common strategy uses the two pointers technique. Start one pointer at 0 and the other at floor(sqrt(c)). Compute the sum of their squares and adjust the pointers depending on whether the value is smaller or larger than c. This works because increasing one pointer increases the sum while decreasing the other reduces it.
Another idea is to iterate over possible values of a and use binary search to check if c - a² is a perfect square. Both methods rely on mathematical bounds and efficient searching rather than brute force. The two‑pointer method typically achieves O(√c) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers | O(√c) | O(1) |
| Iterate + Binary Search | O(√c log c) | O(1) |
NeetCode
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)
1#include <stdbool.h>
2#include <math.h>
3
4bool judgeSquareSum(int c) {
5 int a = 0;
6We use a two-pointer approach with a starting from 0 and b from the square root of c. We check the sum of squares and return accordingly.
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, binary search can be used as an alternative approach. For each possible value of a, compute c − a² and check if the result is a perfect square using binary search. While effective, it is usually slightly slower than the two‑pointer approach.
Yes, this problem is a common interview question because it tests mathematical thinking, boundary analysis, and search techniques like two pointers or binary search. Variations of this concept appear in interviews at major tech companies.
The most efficient approach uses the two pointers technique. One pointer starts at 0 and the other at floor(sqrt(c)), and their squared sum is adjusted by moving pointers until the target is found or the pointers cross. This method runs in O(√c) time with constant space.
No special data structure is required for this problem. The solution mainly relies on mathematical reasoning and pointer movement within a bounded range from 0 to sqrt(c). Simple variables and arithmetic operations are sufficient.
This solution checks every value of a up to sqrt(c) and verifies if c - a^2 is a perfect square.