Perfect Squares — Solution in Python, Java & C++
Perfect Squares solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Perfect Squares is a medium coding problem on dynamic programming, math and breadth-first search, asked in Amazon, Google, Adobe and Meta interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Breadth-First Search
- Asked at: Amazon, Google, Adobe, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return the least number of perfect-square numbers that sum to n.
A perfect square is the product of an integer with itself: 1, 4, 9, 16, …
Example 1
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Example 3
Input: n = 1
Output: 1
Constraints
1 <= n <= 300
Hints for Perfect Squares
Hint 1
This is an unbounded coin-change problem where the coins are the perfect squares up to
n.Hint 2
dp[i] = 1 + min(dp[i - k²])over everykwithk² <= i.Hint 3
Lagrange's four-square theorem guarantees the answer is always 1, 2, 3 or 4.
How to solve Perfect Squares
Unbounded coin change where the coins are the perfect squares: dp[i] = 1 + min(dp[i - k²]) over every k² ≤ i.
Approach
- Set
dp[0] = 0and everything else to a large value. - For each
i, try every squarek² ≤ iand take the minimum. - Return
dp[n].
Why it works
The last square in an optimal representation of i is some k², leaving an optimal representation of i - k²; the recurrence tries every last square.
Complexity
- Time —
O(n · √n) - Space —
O(n)
Pitfalls
- Lagrange's theorem bounds the answer at 4; a number-theory shortcut exists but the DP is the expected approach.
Reference solution
Python
def numSquares(n: int) -> int:
dp = [0] + [n + 1] * n
for i in range(1, n + 1):
k = 1
while k * k <= i:
dp[i] = min(dp[i], dp[i - k * k] + 1)
k += 1
return dp[n]Java
public static int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int k = 1; k * k <= i; k++) {
dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
}
}
return dp[n];
}C++
int numSquares(int n) {
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int k = 1; k * k <= i; k++) {
dp[i] = min(dp[i], dp[i - k * k] + 1);
}
}
return dp[n];
}JavaScript
var numSquares = function(n) {
const dp = new Array(n + 1).fill(n + 1);
dp[0] = 0;
for (let i = 1; i <= n; i++) {
for (let k = 1; k * k <= i; k++) {
if (dp[i - k * k] + 1 < dp[i]) dp[i] = dp[i - k * k] + 1;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Breadth-First Search (BFS)