Understanding the Problem

Given a non-negative integer c, we need to determine if there exist two integers a and b such that a^2 + b^2 = c.

Naive Solution (Brute Force)

A simple approach is to iterate through all possible values of a from 0 up to the square root of c. For each a, we can calculate b^2 = c - a^2. Then, we check if b is an integer by taking the square root of b^2 and verifying if it's an integer.

Code (Python)

import math

def judgeSquareSum_brute_force(c: int) -> bool:
    for a in range(int(math.sqrt(c)) + 1):
        b_squared = c - a * a
        if b_squared >= 0:
            b = math.sqrt(b_squared)
            if b == int(b):
                return True
    return False

Time Complexity

O(sqrt(c)), as we iterate up to the square root of c.

Space Complexity

O(1), as we use only a constant amount of extra space.

Optimal Solution (Two Pointers)

A more efficient approach uses the two-pointer technique. We initialize two pointers, left and right. left starts at 0, and right starts at the square root of c. We then iterate while left <= right. In each iteration, we calculate a^2 + b^2 (where a is left and b is right).

• If the sum is equal to c, we've found a solution, and return True.
• If the sum is less than c, we increment left to increase the sum.
• If the sum is greater than c, we decrement right to decrease the sum.

If we complete the loop without finding a solution, we return False.

Code (Python)

import math

def judgeSquareSum(c: int) -> bool:
    left = 0
    right = int(math.sqrt(c))

    while left <= right:
        sum_of_squares = left * left + right * right

        if sum_of_squares == c:
            return True
        elif sum_of_squares < c:
            left += 1
        else:
            right -= 1

    return False

Time Complexity

O(sqrt(c)), as the two pointers can move at most sqrt(c) times.

Space Complexity

O(1), as we use only a constant amount of extra space.

Edge Cases

• c = 0: In this case, a = 0 and b = 0 is a valid solution.
• c = 1: In this case, a = 1 and b = 0 (or vice versa) is a valid solution.
• Large values of c: The algorithm should handle large values of c without integer overflow issues.