Solution Explanation for LeetCode 633: Sum of Square Numbers

This problem asks whether a non-negative integer c can be expressed as the sum of two squares, i.e., a² + b² = c, where a and b are integers. Two approaches are presented below:

Approach 1: Two Pointers

This approach leverages the fact that if a solution exists, one of the squares (a² or b²) will be less than or equal to c/2. We can use two pointers, a and b, initialized to 0 and √c respectively. We iterate, checking if a² + b² equals c.

• If a² + b² < c, we increment a, effectively searching for a larger a².
• If a² + b² > c, we decrement b, searching for a smaller b².
• If a² + b² == c, we've found a solution, and return true.
• The loop continues until a surpasses b. If no solution is found, we return false.

Time Complexity: O(√c). The loop iterates at most √c times. Space Complexity: O(1). Constant extra space is used.

Code (Python):

import math
 
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a, b = 0, int(math.sqrt(c))
        while a <= b:
            square_sum = a**2 + b**2
            if square_sum == c:
                return True
            elif square_sum < c:
                a += 1
            else:
                b -= 1
        return False

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same logic, with minor syntactic differences.

Approach 2: Mathematical Theorem

A more mathematically elegant solution utilizes a theorem from number theory:

A positive integer n can be written as the sum of two squares if and only if each prime factor p of n such that p ≡ 3 (mod 4) has an even exponent in the prime factorization of n.

This means we need to find the prime factorization of c. For every prime factor of the form 4k + 3, its exponent must be even for c to be representable as a sum of two squares.

Time Complexity: O(√c). Dominated by prime factorization (though optimizations exist). Space Complexity: O(1). Constant extra space.

Code (Python):

import math
 
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        for i in range(2, int(math.sqrt(c)) + 1):
            if c % i == 0:
                exponent = 0
                while c % i == 0:
                    c //= i
                    exponent += 1
                if i % 4 == 3 and exponent % 2 != 0:
                    return False
        return c % 4 != 3

This code iterates through potential prime factors up to √c. If a factor of the form 4k+3 has an odd exponent, it returns False. Otherwise, it checks if the remaining c is not congruent to 3 (mod 4).

Conclusion:

Both approaches solve the problem correctly. The two-pointer approach is generally simpler to understand and implement, while the mathematical approach offers a more theoretically grounded solution. The choice depends on the prioritization of simplicity versus mathematical elegance. The time complexity is asymptotically similar for both.