Sum of Square Numbers

Medium
758.

Sum of Square Numbers

Sum of Square Numbers is a medium coding problem on math, binary search and two pointers, asked in Amazon, Google and Adobe interviews.

Given a non-negative integer c, decide whether there exist non-negative integers a and b with a² + b² == c.

Return true if such a pair exists.

Example 1

Input
c = 5
Output
true
Explanation
1² + 2² = 5.

Example 2

Input
c = 3
Output
false

Example 3

Input
c = 4
Output
true
Explanation
0² + 2² = 4.

Constraints

  • 0 <= c <= 10000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Square Numbers — Solution in Python, Java & C++

Sum of Square Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sum of Square Numbers is a medium coding problem on math, binary search and two pointers, asked in Amazon, Google and Adobe interviews.

Problem statement

Given a non-negative integer c, decide whether there exist non-negative integers a and b with a² + b² == c.

Return true if such a pair exists.

Example 1

Input: c = 5
Output: true
Explanation: 1² + 2² = 5.

Example 2

Input: c = 3
Output: false

Example 3

Input: c = 4
Output: true
Explanation: 0² + 2² = 4.

Constraints

  • 0 <= c <= 10000000

Hints for Sum of Square Numbers

  1. Hint 1

    Both squares are at most c, so a and b lie between 0 and floor(sqrt(c)).

  2. Hint 2

    Two pointers from the ends of that range work: the sum increases with a and decreases with b.

  3. Hint 3

    Compute the integer square root by a loop rather than a floating-point sqrt.

How to solve Sum of Square Numbers

Search the pair (a, b) with a <= b <= sqrt(c) using two pointers. The sum a² + b² rises when a rises and falls when b falls, so every candidate is covered in one sweep.

Approach

  1. Find the largest b with b² <= c by an integer loop.
  2. Start a at 0 and compare a² + b² with c.
  3. Increase a when the sum is too small; decrease b when it is too large; report success on equality.
  4. Stop when the pointers cross.

Why it works

Any solution has a <= b after swapping, and both are at most sqrt(c). The sweep is monotone in both directions, so it neither skips a solution nor revisits a pair.

Complexity

  • Time — O(sqrt(c))
  • Space — O(1)

Pitfalls

  • A floating-point sqrt can land one off on a perfect square, and the judge's C harness has no math.h — the integer loop avoids both.
  • a and b may be zero, so c = 0 and c = 4 both answer true.
  • b * b stays inside 32 bits at this limit, but at LeetCode's real bound it needs a wider type.

Reference solution

Python

def judgeSquareSum(c: int) -> bool:
    a, b = 0, 0
    while (b + 1) * (b + 1) <= c:
        b += 1
    while a <= b:
        total = a * a + b * b
        if total == c:
            return True
        if total < c:
            a += 1
        else:
            b -= 1
    return False

Java

public static boolean judgeSquareSum(int c) {
    long a = 0, b = 0;
    while ((b + 1) * (b + 1) <= c) b++;
    while (a <= b) {
        long sum = a * a + b * b;
        if (sum == c) return true;
        if (sum < c) a++;
        else b--;
    }
    return false;
}

C++

bool judgeSquareSum(int c) {
    long long a = 0, b = 0;
    while ((b + 1) * (b + 1) <= c) b++;
    while (a <= b) {
        long long sum = a * a + b * b;
        if (sum == c) return true;
        if (sum < c) a++;
        else b--;
    }
    return false;
}

JavaScript

var judgeSquareSum = function(c) {
    var a = 0, b = 0;
    while ((b + 1) * (b + 1) <= c) b++;
    while (a <= b) {
        var sum = a * a + b * b;
        if (sum === c) return true;
        if (sum < c) a++;
        else b--;
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search · Two Pointers Technique