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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Square Numbers

Number: 633

Difficulty: Medium

Paid? No

Companies: Bloomberg, Meta, Microsoft, Google, Amazon, Apple, LinkedIn

Problem Description

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

Key Insights

  • Use a two-pointer approach where one pointer (a) starts from 0 and the other pointer (b) starts from the integer square root of c.
  • At each step, compute the sum of squares (a² + b²) and compare it with c.
  • If the sum is less than c, increment a to get a larger value; if the sum is greater than c, decrement b to get a smaller value.
  • Continue until the pointers meet. If a valid pair is found, return true; otherwise, return false.

Space and Time Complexity

Time Complexity: O(√c) - In the worst-case scenario, both pointers traverse the number line up to the square root of c. Space Complexity: O(1) - Only constant extra space is used.

Solution

The solution uses a two-pointer technique with one pointer (a) starting at 0 and the other pointer (b) starting at the floor of √c. We iterate using the following logic:

  1. Calculate the sum of squares: currentSum = a² + b².
  2. If currentSum equals c, a valid pair (a, b) is found and the function returns true.
  3. If currentSum is less than c, increment a to increase the sum.
  4. If currentSum is greater than c, decrement b to decrease the sum.
  5. Repeat the process until a > b. If no pair is found, return false. This method ensures an efficient search with minimal iterations.

Code Solutions

def judge_square_sum(c):
    # Initialize two pointers: a starts at 0, b starts at the floor of sqrt(c)
    a = 0
    b = int(c ** 0.5)
    # Iterate until a exceeds b
    while a <= b:
        current_sum = a * a + b * b  # Calculate sum of squares
        # Check if the sum matches the target c
        if current_sum == c:
            return True  # Found valid integers a and b that satisfy a^2 + b^2 = c
        # If the current sum is less than c, increment a to increase the sum
        elif current_sum < c:
            a += 1
        # If the current sum is greater than c, decrement b to decrease the sum
        else:
            b -= 1
    return False  # No valid pair found

# Example usage
print(judge_square_sum(5))  # Expected output: True
print(judge_square_sum(3))  # Expected output: False
← Back to All Questions