Perfect Squares
MedPrompt
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Constraints:
1 <= n <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
Use recursion to try all possible combinations of perfect squares that sum up to n.
Algorithm
- Create a recursive helper function that takes the remaining number n
- Base cases:
- If n is 0, return 0
- If n is negative, return MAX_VALUE
- For each number i from 1 to sqrt(n):
- Subtract i*i from n
- Recursively find minimum squares for remaining number
- Update minimum if a valid solution is found
- Return minimum + 1
Walkthrough
This approach uses recursion to find all possible combinations of perfect squares that sum up to n. For each number from 1 to sqrt(n), we try subtracting its square from n and recursively find the minimum number of perfect squares needed for the remaining number.
class Solution { public int numSquares(int n) { if (n <= 0) return 0; return recursiveHelper(n); } private int recursiveHelper(int n) { if (n == 0) return 0; if (n < 0) return Integer.MAX_VALUE; int min = Integer.MAX_VALUE; for (int i = 1; i * i <= n; i++) { int result = recursiveHelper(n - i * i); if (result != Integer.MAX_VALUE) { min = Math.min(min, result + 1); } } return min; }}Complexity
Time
O(n^(h/2)) where h is the height of recursion tree
Space
O(sqrt(n)) for recursion stack
Trade-offs
Pros
Simple to understand and implement
Works for small inputs
Cons
Exponential time complexity
Stack overflow for large inputs
Many redundant calculations
Solutions
Solution
class Solution { public int numSquares ( int n ) { int m = ( int ) Math . sqrt ( n ); int [] f = new int [ n + 1 ]; Arrays . fill ( f , 1 << 30 ); f [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i * i ; j <= n ; ++ j ) { f [ j ] = Math . min ( f [ j ], f [ j - i * i ] + 1 ); } } return f [ n ]; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.