NeetCode #924LC-633MediumMath & Geometry
← Back to All Problems#924 · #633 · Sum of Square Numbers(平方数之和)
📌 Problem Statement & Constraints
Given a non-negative integer
c, decide whether there exist integers a and b such that a^2 + b^2 = c. Constraints: 0 <= c <= 2^31 - 1.💡 Core Algorithmic Approaches
- Use two pointers
aandbover the range[0, isqrt(c)], starting at the two extremes. - If
a^2 + b^2 == c, a solution exists; if the sum is less thanc, incrementa; if it is greater, decrementb. - Because increasing
aonly increases the sum and decreasingbonly decreases it, the pointers sweep every candidate pair exactly once. - An alternative enumerates
aand tests whetherc - a^2is a perfect square using an exact integer square root.
💻 Benchmark Python3 Implementation
class Solution:
def judgeSquareSum(self, c: int) -> bool:
from math import isqrt
lo, hi = 0, isqrt(c) # exact integer sqrt, no float error
while lo <= hi:
s = lo * lo + hi * hi
if s == c:
return True
if s < c:
lo += 1 # need a larger sum
else:
hi -= 1 # need a smaller sum
return False
# Alternative: fix `a` and test whether `c - a*a` is a perfect square
class Solution2:
def judgeSquareSum(self, c: int) -> bool:
from math import isqrt
a = 0
while a * a <= c:
b2 = c - a * a
b = isqrt(b2)
if b * b == b2:
return True
a += 1
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(sqrt(c)): the two pointers advance a total of O(sqrt(c)) steps.
💾 Space Complexity
O(1).
⚠️ Interview Pitfalls & Follow-ups
- Using
int(c0.5) as the upper bound**: floating-point error can make it off by one for largec;math.isqrtis exact. - Testing
bwithmath.sqrt: the float result can misjudge perfect squares near the 2^31 boundary; compare integer squares instead. - Adding symmetry handling for
a <= b: the two-pointer sweep already covers both orders, so no extra case analysis is needed. - Forgetting
c = 0:0 = 0^2 + 0^2, so the answer istrue; the initiallo = hi = 0handles it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.