#633

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Sum of Square Numbers

Given a non-negative integer c, determine if there are two integers whose squares sum to c.

Problem Statement

Given a non-negative integer c, decide whether there exist two integers a and b such that a^2 + b^2 = c. The goal is to return true if such integers exist, otherwise false.

For example, for c = 5, the integers a = 1 and b = 2 satisfy the equation 1^2 + 2^2 = 5, so the output would be true. In contrast, for c = 3, no such integers exist, and the output would be false.

Examples

Example 1

Input: c = 5

Output: true

1 * 1 + 2 * 2 = 5

Example 2

Input: c = 3

Output: false

Example details omitted.

Constraints

0 <= c <= 231 - 1

Solution Approach

Binary Search over the answer space

The core approach involves using binary search over the range of potential values for the integers a and b. The idea is to check if the square of one number can be subtracted from c to yield a perfect square, which helps narrow down the possibilities efficiently.

Two Pointers Approach

Another efficient method to solve this problem is by using the two-pointer technique. You can start with one pointer at 0 and the other at sqrt(c), iterating while adjusting the pointers until you either find a match or exhaust the possibilities.

Mathematical Approach

An alternate solution involves mathematical insights into perfect squares. We can check for each candidate square if the remaining difference is also a perfect square using integer square roots.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. Using binary search, the time complexity is O(sqrt(c)), as we search through potential values of a and b. The space complexity is O(1), as only a few variables are used during execution.

What Interviewers Usually Probe

Tests the candidate's ability to apply binary search over a valid range efficiently.
Assesses understanding of two-pointer techniques in algorithmic problem-solving.
Evaluates the candidate's ability to recognize patterns in math-based problems.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the search space, leading to unnecessarily complex solutions.
Overcomplicating the problem and missing simpler solutions like binary search or two-pointer.
Not handling edge cases such as c = 0 correctly.

Follow-up variants

What if the sum of squares must be divisible by a certain number?
What if negative numbers were allowed for a and b?
What if the problem asked for more than two squares to sum up to c?

FAQ

How can binary search help with the Sum of Square Numbers problem?

Binary search can efficiently narrow down the possible values for the integers a and b by searching the range for valid square sums.

What’s the optimal time complexity for the Sum of Square Numbers problem?

The optimal time complexity is O(sqrt(c)) when using binary search or two-pointer approaches.

Are there any edge cases to consider when solving this problem?

Yes, especially when c is 0, where the solution is trivially true (since 0^2 + 0^2 = 0).

Can two-pointer or binary search be used to solve this problem efficiently?

Yes, both techniques are efficient for this problem. Binary search can be used to explore the possible squares, and two-pointer works well by checking sums incrementally.

How do I optimize my solution for the Sum of Square Numbers problem?

You can optimize your solution by limiting the search space using binary search or the two-pointer technique, both of which offer O(sqrt(c)) time complexity.

terminal

Solution

Solution 1: 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`.

1

2

3

4

5

6

7

8

9

10

11

12

class 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

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

class 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

Continue Practicing

#1237 find positive integer solution for a given equation #611 valid triangle number #658 find k closest elements