⚡Flashcard Drill➔
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

  1. Use two pointers a and b over the range [0, isqrt(c)], starting at the two extremes.
  2. If a^2 + b^2 == c, a solution exists; if the sum is less than c, increment a; if it is greater, decrement b.
  3. Because increasing a only increases the sum and decreasing b only decreases it, the pointers sweep every candidate pair exactly once.
  4. An alternative enumerates a and tests whether c - a^2 is 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(c 0.5) as the upper bound**: floating-point error can make it off by one for large c; math.isqrt is exact.
  • Testing b with math.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 is true; the initial lo = hi = 0 handles it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems