633. Sum of Square Numbers
Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 32.6%
Problem Breakdown
We are given a non-negative integer c and need to determine if it can be represented as the sum of two perfect squares (). The inputs are integers, so we don’t have floating-point precision issues. Since , negative values for a or b do not provide new solutions compared to their positive counterparts; thus, we only need to consider non-negative integers for our search space.
Key constraints:
- Input range is up to the maximum 32-bit signed integer ().
- Output must be a boolean (
TrueorFalse). - Edge case: . Since , this should return
true.
Intuition
A brute-force approach would iterate through all possible values for both a and b, which is inefficient (). A slightly better but still suboptimal method iterates one variable (say, a) from to and checks if the remainder is a perfect square. While this works, we can optimize using monotonicity.
Consider the equation , where . As a increases (moving right), its contribution to the sum grows monotonically. To maintain the total sum equal to c, if one term gets larger, the other must get smaller. This suggests a Two Pointers approach on the range of possible values . We start with the smallest possible square () and the largest possible square that doesn’t exceed c (). If our current sum is less than c, we need a larger value for one of them, so we increment the smaller pointer. Conversely, if it’s too large, we decrement the larger pointer. This narrows down to either finding the match or exhausting the search space without redundant checks.
Approach
- Initialize two pointers:
leftat andrightat . We calculate this initial bound once because any value greater than would result in a square larger thanc, making the sum exceedc. - Loop while
left <= right:- Calculate current sum: .
- If , we found valid integers; return
True. - If , increment
leftto increase the sum (since increasing a square increases total). - If , decrement
rightto decrease the sum.
- If the loop completes without finding a match, return
False.
Complexity Analysis
- Time Complexity: . The pointers start at opposite ends of the range and move towards each other. In the worst case (e.g., no solution exists), we iterate roughly times because
leftincreases by 1 in every step where sum < c or right decreases similarly. - Space Complexity: . We only use a few integer variables for pointers and calculations, regardless of input size.
Solution
import math
def judgeSquareSum(c: int) -> bool:
# Initialize left pointer at 0 (smallest possible square contribution)
left = 0
# Initialize right pointer to the largest integer whose square <= c
# Using isqrt for efficient integer square root calculation in Python 3.8+
right = math.isqrt(c)
while left <= right:
current_sum = left * left + right * right
if current_sum == c:
return True
elif current_sum < c:
# Need a larger sum, increment the smaller number's square
left += 1
else:
# Sum is too large, decrement the larger number's square
right -= 1
return False
Edge Cases Handled
c = 0:left=0,right=0. Loop runs once. . ReturnsTrue. Correctly handles the zero case where both integers are 0.- Large Primes (e.g., non-square sums): The pointers will cross each other (
left > right) without finding a match, correctly returningFalseafter exhausting valid ranges. - Perfect Squares: If is a perfect square like 4 (), the logic finds it when one pointer hits 0 and the other hits .