algoadvance

Given a non-negative integer c, determine whether there are two integers a and b such that:

[ a^2 + b^2 = c ]

Clarifying Questions

  1. Can a and b be the same number?
    • Yes, a and b can be the same or different as long as ( a^2 + b^2 = c ).
  2. What is the range of c?
    • c is a non-negative integer and can range from 0 to ( 2^{31} - 1 ).
  3. Do we need to consider negative numbers for a and b?
    • No, since squaring negative numbers or positive numbers results in the same outcome, we can restrict ( a ) and ( b ) to non-negative integers only.

Strategy

To solve the problem efficiently, we can use the following approach:

  1. Initialize two pointers:
    • a starting at 0.
    • b starting at ( \sqrt{c} ).
  2. Use a two-pointer technique to iterate and check:
    • Calculate the sum of squares ( a^2 + b^2 ).
    • If ( a^2 + b^2 = c ), return True.
    • If ( a^2 + b^2 < c ), increment a to increase the sum.
    • If ( a^2 + b^2 > c ), decrement b to decrease the sum.
  3. If the loop completes without finding a solution, return False.

Code

Here’s the code implementing the above strategy:

import math

def judgeSquareSum(c):
    # Initialize pointers
    a = 0
    b = int(math.sqrt(c))
    
    while a <= b:
        current_sum = a * a + b * b
        if current_sum == c:
            return True  # Found the integers a and b such that a^2 + b^2 = c
        elif current_sum < c:
            a += 1  # Increase the sum by increasing a
        else:
            b -= 1  # Decrease the sum by decreasing b
    
    return False  # No such integers found

# Example usage:
c = 5
print(judgeSquareSum(c))  # Output: True, since 1^2 + 2^2 = 5

Time Complexity

The time complexity of this approach is ( O(\sqrt{c}) ) because in the worst case, the a pointer will iterate from 0 to ( \sqrt{c} ), and the b pointer will iterate from ( \sqrt{c} ) back down to 0.

The space complexity is ( O(1) ) because we are using a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com