279. Perfect Squares - Detailed Explanation

Problem Statement

Given a positive integer n, find the smallest number of perfect square numbers (e.g. 1, 4, 9, 16, …) whose sum equals n. Return that minimum count.

Examples

Input   n = 12  
Output  3  
Explanation  12 = 4 + 4 + 4

Input   n = 13  
Output  2  
Explanation  13 = 4 + 9

Constraints

1 ≤ n ≤ 10⁴

Hints

You can view the problem as finding the shortest path from n down to 0 by subtracting squares.
For dynamic programming, think about how the solution for n depends on smaller values n - k².
A theorem says every positive integer is the sum of at most four squares—can you use that to shortcut for some cases?

Approach 1 – BFS over States

You can treat each integer x from n down to 0 as a node; edges go from x to x - k² for all k² ≤ x. A breadth‑first search from n stops at 0 with the shortest distance equal to the answer.

Python Code

Python3

. . . .

Time: O(n √n) in practice
Space: O(n) for the queue and visited set

Approach 2 – Dynamic Programming

Define dp[i] = minimum number of squares summing to i. Then

dp[0] = 0  
for i in 1…n:  
  dp[i] = min(dp[i - k²] + 1 for k² ≤ i)

Python Code

Python3

. . . .

Java Code

Java

. . . .

Time: O(n √n)
Space: O(n)

Approach 3 – Mathematical Theorem (Lagrange’s Four‑Square)

A classic result says every natural number is the sum of at most four squares. You can check in O(√n) time whether it is 1‑, 2‑, or 3‑square representable; otherwise the answer is 4.

If n is a perfect square → return 1.
Remove factors of 4 from n (while divisible by 4, divide by 4).
If n ≡ 7 mod 8 → return 4.
Check if n = a² + b² for some a,b → return 2.
Otherwise → return 3.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Time: O(√n)
Space: O(1)

Complexity Analysis

BFS/DP: O(n √n), O(n) space
Math: O(√n), O(1) space

Step‑by‑Step Walkthrough (n = 12)

DP:
- dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=1, … dp[12]=dp[12‑9]+1=dp[3]+1=4 → but a better is dp[12‑4]+1=dp[8]+1= (dp[8‑4]+1)+1 = … =3
Math:
- 12 not square, not ≡7 mod8 after dividing by 4⁰, check two‑square: 12–1²=11 not square, 12–2²=8 not square, 12–3²=3 not square → return 3.

Common Mistakes

Forgetting to initialize dp[0]=0.
In DP, iterating j too far (stop when j²>i).
In math approach, skipping the “remove factors of 4” step and misclassifying 28 as 4‑case.