Sum of Square Numbers - Solution & Explanation
Problem Statement
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 - 1
Approach Overview
Problem 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.
Approach 1: Using Two Pointers
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.
Complexity
Time Complexity: O(sqrt(c))
Space Complexity: O(1)
Approach 2: Mathematical Interpretation and Brute Force
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.
Complexity
Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check.
Space Complexity: O(1)
Approach 3: Mathematics + Two Pointers
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).
Approach 4: Mathematics
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:
- The number
13is a prime and13 \equiv 1 \pmod{4}, so it can be expressed as the sum of two squares, i.e.,13 = 2^2 + 3^2. - The number
21can be decomposed into3 times 7, where both3and7are prime factors of the form4k + 3and their exponents are1(odd), so21cannot 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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Sum of Square Numbers - Leetcode 633 - Python • NeetCodeIO • 15,847 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sum of Square Numbers easy or hard?
Sum of Square Numbers Python/Java solution
How to solve Sum of Square Numbers in O(n)?
What is the best approach for Sum of Square Numbers?
Is Sum of Square Numbers asked at Google/Amazon/Meta?
What data structure is used in Sum of Square Numbers?
What is the time complexity of Sum of Square Numbers?
Ready to solve this problem?
Practice Sum of Square Numbers with our built-in code editor and test cases.
Practice on FleetCode