Sum of Square Numbers

LeetCode 633 | Difficulty: Medium

Medium

Problem Description

Given a non-negative integer c, decide whether there're two integers a and b such that a^2 + b^2 = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Constraints:

- `0 <= c <= 2^31 - 1`

Topics: Math, Two Pointers, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 548 ms)

Metric	Value
Runtime	548 ms
Memory	28.5 MB
Date	2020-02-11

Solution

public class Solution {
    public bool JudgeSquareSum(int c) {
        SortedSet<int> squares = new SortedSet<int>();
    double val = Math.Floor(Math.Sqrt(c));
    
    for (int i = 0; i <= val; i++)
    {
        squares.Add(i*i);
    }
    
    foreach (var e in squares)
    {
        if(squares.Contains(c-e)) return true;
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.