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 - 1Problem Overview: Given a non‑negative integer c, determine whether there exist integers a and b such that a² + b² = c. The task is essentially checking whether the number can be represented as the sum of two perfect squares.
Approach 1: Mathematical Interpretation and Brute Force (O(√c) time, O(1) space)
The direct way is to iterate one value and check whether the remaining value forms a perfect square. Loop a from 0 to sqrt(c). For each value, compute b² = c - a² and check if b² is a perfect square using sqrt() or an integer check. If b * b == b², the equation holds and the answer is true. This works because a cannot exceed √c, which limits the search space significantly. The approach relies heavily on math reasoning about perfect squares and avoids checking every pair of numbers.
Approach 2: Two Pointers (O(√c) time, O(1) space)
This method treats the possible square values like a sorted range and applies the classic two pointers pattern. Initialize left = 0 and right = floor(sqrt(c)). Compute sum = left² + right². If the sum equals c, a valid pair exists. If the sum is smaller, increment left to increase the value. If the sum is larger, decrement right to reduce it. Because squares grow monotonically, this pointer movement systematically explores all combinations without nested loops. The technique mirrors the two‑sum pattern on a sorted array of square values.
Some implementations replace the perfect square check with a binary search on b, but that increases the time complexity to O(√c log c). The two‑pointer approach achieves the same goal with fewer operations and simpler logic.
Recommended for interviews: Start with the mathematical brute force idea to show you recognize the constraint a ≤ √c. Then move to the two‑pointer approach. Interviewers typically expect this optimization because it demonstrates pattern recognition and efficient search on a monotonic range while maintaining constant space.
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.
We 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.
Time Complexity: O(sqrt(c))
Space Complexity: O(1)
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.
This solution checks every value of a up to sqrt(c) and verifies if c - a^2 is a perfect square.
Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check.
Space Complexity: O(1)
We can use the two-pointer method to solve this problem. Define two pointers a and b, pointing to 0 and \sqrt{c} respectively. In each step, we calculate the value of s = a^2 + b^2, and then compare the size of s and c. If s = c, we have found two integers a and b such that a^2 + b^2 = c. If s < c, we increase the value of a by 1. If s > c, we decrease the value of b by 1. We continue this process until we find the answer, or the value of a is greater than the value of b, and return false.
The time complexity is O(\sqrt{c}), where c is the given non-negative integer. The space complexity is O(1).
This problem is essentially about the conditions under which a number can be expressed as the sum of two squares. This theorem dates back to Fermat and Euler and is a classic result in number theory.
Specifically, the theorem can be stated as follows:
A positive integer
ncan be expressed as the sum of two squares if and only if all prime factors ofnof the form4k + 3have even powers.
This means that if we decompose n into the product of its prime factors, n = p_1^{e_1} p_2^{e_2} cdots p_k^{e_k}, where p_i are primes and e_i are their corresponding exponents, then n can be expressed as the sum of two squares if and only if all prime factors p_i of the form 4k + 3 have even exponents e_i.
More formally, if p_i is a prime of the form 4k + 3, then for each such p_i, e_i must be even.
For example:
13 is a prime and 13 \equiv 1 \pmod{4}, so it can be expressed as the sum of two squares, i.e., 13 = 2^2 + 3^2.21 can be decomposed into 3 times 7, where both 3 and 7 are prime factors of the form 4k + 3 and their exponents are 1 (odd), so 21 cannot be expressed as the sum of two squares.In summary, this theorem is very important in number theory for determining whether a number can be expressed as the sum of two squares.
The time complexity is O(\sqrt{c}), where c is the given non-negative integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using Two Pointers | Time Complexity: O(sqrt(c)) |
| Mathematical Interpretation and Brute Force | Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check. |
| Mathematics + Two Pointers | — |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mathematical Brute Force (check perfect square) | O(√c) | O(1) | Good baseline approach. Simple logic when you only need to check one candidate per iteration. |
| Two Pointers | O(√c) | O(1) | Preferred interview solution. Efficient exploration of pairs without nested loops. |
| Binary Search for Second Square | O(√c log c) | O(1) | Useful if you want explicit search for the second value instead of pointer movement. |
Sum of Square Numbers - Leetcode 633 - Python • NeetCodeIO • 15,508 views views
Watch 9 more video solutions →Practice Sum of Square Numbers with our built-in code editor and test cases.
Practice on FleetCode