We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Square Numbers

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires finding two integers whose squares sum up to a given number.
  • We can utilize the properties of squares and leverage a two-pointer technique or binary search for efficiency.
  • The maximum value for a and b can be derived from the square root of c.

Space and Time Complexity

Time Complexity: O(√c)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer approach. We first identify the maximum possible integer a (which is the integer part of the square root of c). Then, we can set one pointer at 0 (for a) and the other pointer at the maximum integer (for b). We check the sum of squares of these two pointers:

  • If the sum equals c, we return true.
  • If the sum is less than c, we increment the first pointer to increase the sum.
  • If the sum is greater than c, we decrement the second pointer to decrease the sum. This continues until the pointers meet or we find a valid pair.

Code Solutions

def judgeSquareSum(c):
    left, right = 0, int(c**0.5)
    while left <= right:
        sum_squares = left * left + right * right
        if sum_squares == c:
            return True
        elif sum_squares < c:
            left += 1
        else:
            right -= 1
    return False
← Back to All Questions