Perfect Squares
Problem Statement
Given an integer n, return the least number of perfect square numbers whose sum is n. A perfect square is an integer of the form k * k, such as 1, 4, 9, or 16.
Input
A single integer n.
Output
An integer: the minimum number of perfect squares that sum to n.
Constraints
- •
1 <= n <= 10000
Examples
Example 1
n = 12
3Example 2
n = 13
2Example 3
n = 1
1Learning Objectives
- Recognise perfect squares as reusable pieces for building every amount up to **n**.
- Define **dp[i]** as a minimum count rather than a boolean reachability state.
- Derive the recurrence by choosing the last square used in the sum.
- Connect the problem to unbounded knapsack because each square may be used repeatedly.
Intuition
For any target amount i, imagine the last square you decide to use. If that square is k * k, then the remaining amount is i - k * k. The best way to finish that remainder is already stored in dp[i - k * k] once we process amounts from small to large.
So every square gives one candidate answer: solve the remainder optimally, then add this one square. The minimum over all square choices is the best answer for i.
This is unbounded-knapsack-flavoured because using a square does not consume it. After taking 4 once, the subproblem may take 4 again, which is exactly how 12 becomes 4 + 4 + 4.
Common mistakes
- ×Using a greedy largest-square-first strategy; for many values, the locally largest square does not prove optimality.
- ×Forgetting **dp[0] = 0**, the base that makes an exact square cost one piece.
- ×Initialising every **dp[i]** to 0, which makes unsolved states look better than real candidates.
- ×Treating each perfect square as usable only once, even though the same square can appear multiple times.
- ×Looping only over square values already less than **n** and accidentally missing the case where **i** itself is a square.
State Definition
Let dp[i] be the minimum number of perfect squares needed to sum exactly to i. The answer is dp[n].
State Transition
For each amount i, try every square k * k <= i as the last chosen piece:
dp[i] = min over k * k <= i of dp[i - k * k] + 1
The base case is dp[0] = 0 because zero squares are needed to make amount 0. All positive states start at a large sentinel value and are improved by valid square choices.
Solutions
Solution: Bottom-up minimum-count DP
Use this when the interviewer expects a DP derivation. It is deterministic, simple to justify, and mirrors the coin-change minimum-count pattern with square numbers as the coin set.
Build answers for amounts from 1 through n. For each amount, test every square not exceeding it. The candidate count is one chosen square plus the best count for the remaining amount. Keep the smallest candidate.
Step-by-step
- Create dp of size n + 1 and fill it with n + 1, a safe value larger than any possible answer.
- Set dp[0] = 0.
- For each amount from 1 to n, enumerate bases base while base * base <= amount.
- Let square = base * base and relax dp[amount] with dp[amount - square] + 1.
- Return dp[n] after all smaller amounts have been solved.
O(n · sqrt(n))
O(n)
Each amount tries all square numbers up to itself, and the table stores one value per amount.
Java implementation
Dry Run
Sample input
n = 12. Build dp[amount] from 0 to 12 using square choices 1, 4, and 9 where applicable.
| amount | squares tried | best expression | dp[amount] |
|---|---|---|---|
| 0 | none | empty sum | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 + 1 | 2 |
| 3 | 1 | 1 + 1 + 1 | 3 |
| 4 | 1, 4 | 4 | 1 |
| 5 | 1, 4 | 4 + 1 | 2 |
| 6 | 1, 4 | 4 + 1 + 1 | 3 |
| 7 | 1, 4 | 4 + 1 + 1 + 1 | 4 |
| 8 | 1, 4 | 4 + 4 | 2 |
| 9 | 1, 4, 9 | 9 | 1 |
| 10 | 1, 4, 9 | 9 + 1 | 2 |
| 11 | 1, 4, 9 | 9 + 1 + 1 | 3 |
| 12 | 1, 4, 9 | 4 + 4 + 4 | 3 |
At amount 12, choosing square 4 leaves amount 8, whose best value is 2. Therefore dp[12] = dp[8] + 1 = 3.
Complexity Analysis
This is the same minimum-count template as unbounded coin change, with the candidate coin list restricted to perfect squares no larger than the current amount.
Bottom-up minimum-count DP
O(n · sqrt(n))
O(n)
Each amount tries all square numbers up to itself, and the table stores one value per amount.
Interview Tips
Name the similarity to Coin Change, but be explicit that the generated coins are 1, 4, 9, ... up to n. Explain why greedy is not the proof you want in a DP interview: the recurrence is what guarantees the global minimum. Keep the base case and sentinel initialisation clear before coding.
Likely follow-ups
- How would you return one actual list of squares that achieves the minimum?
- Can you solve the problem using shortest-path BFS over amounts?
- What changes if only a limited quantity of each square is available?
- How would number-theory results affect the asymptotic complexity?
Similar Problems
Key Takeaways
- Minimum-count DP chooses one final piece and adds one to the solved remainder.
- Perfect Squares is unbounded because the same square may be used repeatedly.
- A large sentinel value prevents unsolved states from winning a minimum comparison.
- The amount loop guarantees every remainder **i - square** has already been computed.