Perfect Squares
Medium · Dynamic Programming · Math · Dynamic Programming · Breadth-First Search
Problem
A perfect square is a whole number that equals some whole number times itself: 1, 4, 9, 16, and so on.
Given a positive integer n, return the fewest perfect squares that add up to exactly n. The same square may be used more than once.
Examples
Input: n = 7 Output: 4
7 = 4 + 1 + 1 + 1, and no sum of three or fewer squares equals 7.
Input: n = 18 Output: 2
18 = 9 + 9.
Input: n = 25 Output: 1
25 is itself a perfect square.
Constraints
- 1 <= n <= 10^4
Approaches
- Baseline: DP over every total up to n — time O(n · √n), space O(n)
Follow-up
Lagrange proved every positive integer is a sum of four squares, and Legendre that it needs all four exactly when it has the form 4^a (8b + 7). So the answer is always 1, 2, 3 or 4, and only "is it 1?" and "is it 2?" need checking: O(√n) in all. The DP is still the general method when the parts are not squares (cubes, coins of any values).
Related problems
Start free on Cariara · Coding problems · System design studio
