Sum of Square Numbers

Med

#0587Time: O(c). The two nested loops each run up to `sqrt(c)` times, leading to `sqrt(c) * sqrt(c) = c` iterations in the worst case.Space: O(1), as we only use a few variables to store the loop counters.2 companies

Patterns

Math Two Pointers

Algorithms

Binary Search

Companies

LinkedIn Two Sigma

Prompt

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Constraints:

0 <= c <= 2³¹ - 1

Approaches

4 approaches with complexity analysis and trade-offs.

This is the most straightforward, brute-force approach. We can check every possible pair of integers (a, b) to see if their squares sum up to c. Since a^2 and b^2 must be less than or equal to c, the values of a and b must be in the range from 0 to sqrt(c).

Algorithm

Iterate a variable a from 0 up to sqrt(c).
Inside this loop, iterate another variable b from 0 up to sqrt(c).
In the inner loop, calculate the sum a*a + b*b.
If the sum equals c, a valid pair (a, b) has been found, so return true.
If the loops complete without finding any such pair, it means no solution exists. Return false.

Walkthrough

We use two nested loops to explore all combinations of a and b. The outer loop iterates a from 0 to sqrt(c), and the inner loop iterates b from 0 to sqrt(c). Inside the inner loop, we calculate a^2 + b^2 and check if it equals c. If it does, we've found a solution and can return true immediately. If the loops complete without finding such a pair, it means no solution exists, and we return false. To avoid potential integer overflow when calculating a*a + b*b for large c, it's safer to use a long data type for the loop variables and the sum.

1class Solution {2    public boolean judgeSquareSum(int c) {3        for (long a = 0; a * a <= c; a++) {4            for (long b = 0; b * b <= c; b++) {5                if (a * a + b * b == c) {6                    return true;7                }8            }9        }10        return false;11    }12}

Complexity

Time

O(c). The two nested loops each run up to `sqrt(c)` times, leading to `sqrt(c) * sqrt(c) = c` iterations in the worst case.

Space

O(1), as we only use a few variables to store the loop counters.

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient for large values of c.
Will likely result in a 'Time Limit Exceeded' error on most online judges.

We can significantly optimize the brute-force approach by eliminating the inner loop. Instead of iterating through all possible values of b, we can iterate only through a and then directly calculate the required value of b.

Algorithm

Iterate a from 0 up to sqrt(c).
For each a, calculate the required value for b^2, which is b_squared = c - a*a.
Calculate b = sqrt(b_squared).
Check if b is an integer. A simple way is to check if b is equal to its integer cast, i.e., b == (int)b.
If b is an integer, it means we have found a valid pair, so return true.
If the loop finishes without finding such an a, return false.

Walkthrough

The governing equation is a^2 + b^2 = c. We can rearrange it to solve for b: b^2 = c - a^2, which implies b = sqrt(c - a^2). This insight allows us to use a single loop. We iterate a from 0 to sqrt(c). In each iteration, we calculate the value that b^2 would need to be: c - a*a. Then, we take the square root of this result to find b. If this b is a whole number, we have found a valid pair (a, b) and can return true. We can check if b is an integer by comparing it with its truncated version (int)b.

1class Solution {2    public boolean judgeSquareSum(int c) {3        for (long a = 0; a * a <= c; a++) {4            double b = Math.sqrt(c - a * a);5            if (b == (int) b) {6                return true;7            }8        }9        return false;10    }11}

Complexity

Time

O(sqrt(c) * log(c)). The loop runs `sqrt(c)` times. Inside the loop, `Math.sqrt` is called, which typically has a time complexity of O(log c).

Space

O(1), as only a few variables are needed.

Trade-offs

Pros

Much faster than the nested loop approach.
Still relatively simple to understand.

Cons

Relies on floating-point arithmetic, which can have precision issues, though it's generally safe for this problem.
The Math.sqrt function call inside the loop can be less performant than pure integer arithmetic.

This efficient approach treats the problem as a search on a sorted range. We search for two numbers, a and b, in the conceptual range of [0, sqrt(c)]. By using two pointers starting from the ends of this range, we can cleverly narrow down the search space.

Algorithm

Initialize two pointers: left = 0 and right = (long)Math.sqrt(c).
Loop as long as left <= right.
Calculate the current sum of squares: sum = left*left + right*right.
If sum == c, a solution is found, return true.
If sum < c, the sum is too small. To increase it, increment the left pointer: left++.
If sum > c, the sum is too large. To decrease it, decrement the right pointer: right--.
If the loop completes without finding a solution, return false.

Walkthrough

We initialize two pointers: a left pointer starting at 0 and a right pointer starting at (int)sqrt(c). These represent our candidate values for a and b. We then loop as long as left <= right. In each iteration, we compute the sum of squares sum = left*left + right*right.

If sum equals c, we've found our pair, and we can return true.
If sum is less than c, it means our sum is too small. To get a larger sum, we need to increase one of our numbers. Since right is already large, we increase the smaller number by incrementing the left pointer.
If sum is greater than c, our sum is too large. To reduce it, we decrease the larger number by decrementing the right pointer. This process continues until the pointers meet or cross. If the loop finishes, no pair was found, and we return false.

1class Solution {2    public boolean judgeSquareSum(int c) {3        long left = 0;4        long right = (long) Math.sqrt(c);5        while (left <= right) {6            long sum = left * left + right * right;7            if (sum == c) {8                return true;9            } else if (sum < c) {10                left++;11            } else {12                right--;13            }14        }15        return false;16    }17}

Complexity

Time

O(sqrt(c)). The `left` pointer moves from `0` upwards, and the `right` pointer moves from `sqrt(c)` downwards. The pointers will cross in at most `sqrt(c)` steps.

Space

O(1). We only use a few variables for the pointers and the sum.

Trade-offs

Pros

Highly efficient with a linear scan over the search space.
Easy to implement and avoids complex math functions or floating-point arithmetic inside the loop.
Generally one of the fastest solutions in practice.

Cons

While efficient, it might be slightly less intuitive than a direct brute-force search for beginners.

This approach leverages a deep result from number theory, specifically Fermat's theorem on sums of two squares. This theorem provides a direct criterion for determining if a number can be written as the sum of two squares based on its prime factorization.

Algorithm

Iterate through potential prime factors i from 2 up to sqrt(c).
If i divides c:
- Count its exponent: while c is divisible by i, increment a counter and divide c by i.
- Check if the prime i is of the form 4k + 3 (i.e., i % 4 == 3).
- If it is, and its exponent is odd, return false immediately.
After the loop, the remaining value of c (if greater than 1) is also a prime factor with an exponent of 1.
Check if this final factor c is of the form 4k + 3. If so, return false.
If all prime factors satisfy the condition, return true.

Walkthrough

The theorem states that a non-negative integer n can be expressed as a sum of two squares if and only if every prime factor of n of the form 4k + 3 appears with an even exponent in its prime factorization.

To apply this, we need to find the prime factors of c and their exponents. We can do this using trial division. We iterate from i = 2 up to sqrt(c). If we find a divisor i, we know it's a prime factor. We then count how many times it divides c to find its exponent. If this prime factor i gives a remainder of 3 when divided by 4, and its exponent is odd, we can conclude from the theorem that c cannot be a sum of two squares and return false. After checking all factors up to sqrt(c), if the remaining c is greater than 1, it is itself a prime factor with an exponent of 1. We must perform the same check on this final factor. If all prime factors of the form 4k+3 have even exponents, we return true.

1class Solution {2    public boolean judgeSquareSum(int c) {3        for (int i = 2; i * i <= c; i++) {4            if (c % i == 0) {5                int count = 0;6                while (c % i == 0) {7                    count++;8                    c /= i;9                }10                if (i % 4 == 3 && count % 2 != 0) {11                    return false;12                }13            }14        }15        // After the loop, if c > 1, the remaining c is a prime factor with exponent 1.16        return c % 4 != 3;17    }18}

Complexity

Time

O(sqrt(c)). The trial division for prime factorization runs up to `sqrt(c)` in the worst case (e.g., when `c` is a large prime).

Space

O(1). Constant extra space is used.

Trade-offs

Pros

Provides an elegant mathematical solution.
Can be very fast if c is composed of small prime factors.

Cons

Relies on non-trivial number theory (Fermat's theorem), making it less intuitive.
The logic involving prime factorization is more complex to implement correctly than the two-pointer approach.

Solutions

Solution

1class Solution { public boolean judgeSquareSum ( int c ) { long a = 0 , b = ( long ) Math . sqrt ( c ); while ( a <= b ) { long s = a * a + b * b ; if ( s == c ) { return true ; } if ( s < c ) { ++ a ; } else { -- b ; } } return false ; } }

1class Solution { public: bool judgeSquareSum ( int c ) { long a = 0 , b = ( long ) sqrt ( c ); while ( a <= b ) { long s = a * a + b * b ; if ( s == c ) return true ; if ( s < c ) ++ a ; else -- b ; } return false ; } };

1class Solution : def judgeSquareSum ( self , c : int ) -> bool : a , b = 0 , int ( sqrt ( c )) while a <= b : s = a ** 2 + b ** 2 if s == c : return True if s < c : a += 1 else : b -= 1 return False

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public boolean judgeSquareSum ( int c ) { long a = 0 , b = ( long ) Math . sqrt ( c ); while ( a <= b ) { long s = a * a + b * b ; if ( s == c ) { return true ; } if ( s < c ) { ++ a ; } else { -- b ; } } return false ; } }

1class Solution { public: bool judgeSquareSum ( int c ) { long a = 0 , b = ( long ) sqrt ( c ); while ( a <= b ) { long s = a * a + b * b ; if ( s == c ) return true ; if ( s < c ) ++ a ; else -- b ; } return false ; } };

1class Solution : def judgeSquareSum ( self , c : int ) -> bool : a , b = 0 , int ( sqrt ( c )) while a <= b : s = a ** 2 + b ** 2 if s == c : return True if s < c : a += 1 else : b -= 1 return False

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.