Scale Engineer

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
MathTwo Pointers
Algorithms
Binary Search
Companies
LinkedInTwo Sigma

Prompt

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

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.

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

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.

Solutions

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 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 →

Next problem