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
Use dynamic programming to store and reuse previously calculated results.
Algorithm
- Create dp array of size n+1 initialized with MAX_VALUE
- Set dp[0] = 0
- For each number i from 1 to n:
- For each perfect square j*j <= i:
- dp[i] = min(dp[i], dp[i - j*j] + 1)
- For each perfect square j*j <= i:
- Return dp[n]
Walkthrough
This approach uses a dynamic programming array dp where dp[i] represents the least number of perfect squares that sum to i. For each number i, we try all possible perfect squares less than or equal to i and take the minimum.
class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; }}Complexity
Time
O(n * sqrt(n))
Space
O(n) for dp array
Trade-offs
Pros
No redundant calculations
Works for all input sizes within constraints
Polynomial time complexity
Cons
Uses extra space
Still not the most efficient solution possible
Use mathematical properties and Lagrange's Four Square theorem to find the answer.
Algorithm
- Check if n is a perfect square
- Check if n can be represented as sum of two squares
- Check if n is in form 4^k(8m + 7)
- If none of above, return 3 (based on theorem)
Walkthrough
This approach uses Lagrange's Four Square theorem which states that every natural number can be represented as the sum of at most four perfect squares. Additionally, we can check if a number can be represented as sum of 1, 2, or 3 squares using mathematical properties.
class Solution { public int numSquares(int n) { // Check if n is a perfect square if (isSquare(n)) return 1; // Check if n can be sum of two squares for (int i = 1; i * i <= n; i++) { if (isSquare(n - i * i)) return 2; } // Check if n = 4^k(8m + 7) while (n % 4 == 0) { n /= 4; } if (n % 8 == 7) return 4; return 3; } private boolean isSquare(int n) { int sqrt = (int) Math.sqrt(n); return sqrt * sqrt == n; }}Complexity
Time
O(sqrt(n))
Space
O(1)
Trade-offs
Pros
Most efficient solution
Constant space complexity
Based on mathematical theorems
Works for all input sizes
Cons
Requires understanding of mathematical theorems
Less intuitive than other approaches
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 ]; } }class Solution { public: int numSquares ( int n ) { int m = sqrt ( n ); int f [ n + 1 ]; memset ( f , 0x3f , sizeof ( f )); f [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i * i ; j <= n ; ++ j ) { f [ j ] = min ( f [ j ], f [ j - i * i ] + 1 ); } } return f [ n ]; } };class Solution : def numSquares ( self , n : int ) -> int : m = int ( sqrt ( n )) f = [ 0 ] + [ inf ] * n for i in range ( 1 , m + 1 ): for j in range ( i * i , n + 1 ): f [ j ] = 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.