Sum of Square Numbers

MEDIUM

Description

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

Checkout 4 different approaches to solve Sum of Square Numbers. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

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.

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.

class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            for (long b = 0; b * b <= c; b++) {
                if (a * a + b * b == c) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the loop counters.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Square Numbers. Click on different languages to view the code.

class 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 ; } }

Video Solution

Watch the video walkthrough for Sum of Square Numbers

Algorithms:

Binary Search

Patterns:

MathTwo Pointers

Companies:

LinkedIn |Two Sigma |