Code Logo

Perfect Squares

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given an integer n, return the least number of perfect square numbers (1, 4, 9, 16, ...) that sum to n. For example, 12 = 4 + 4 + 4, so the answer is 3. 13 = 9 + 4, so the answer is 2.

This is a classic DP problem with the recurrence: for i from 1 to n, dp[i] = min(dp[i], dp[i - j*j] + 1) for all j*j<= i. The base case is dp[0] = 0.

The solution initializes dp[i] = i (worst case: i = 1+1+...+1 with i ones). For each i, try subtracting each perfect square j*j and take the minimum of dp[i - j*j] + 1. This is an unbounded knapSack DP where the items are perfect squares.

Edge cases include n = 0 (return 0), n = 1 (return 1), n where n itself is a perfect square (return 1), and large values up to 10^4 where O(n*sqrt(n)) is acceptable.

The perfect squares problem is an unbounded knapSack DP where the items are square numbers (1, 4, 9, ...) and we want to minimize the count to reach target n. The initial value dp[i] = i represents the worst case of using i ones (1+1+...+1).

For each i, we try subtracting each perfect square j*j<= i and take the minimum of dp[i-j*j] + 1. The inner loop runs sqrt(i) times, giving O(n*sqrt(n)) overall. This is optimal for n up to 10^4 in typical constraints.

Example Input & Output

Example 1
Input
7
Output
4
Explanation

7 = 4+1+1+1 (4 squares).

Example 2
Input
1
Output
1
Explanation

1 = 1.

Example 3
Input
12
Output
3
Explanation

12 = 4+4+4 (3 squares).

Example 4
Input
0
Output
0
Explanation

Zero needs no squares.

Example 5
Input
13
Output
2
Explanation

13 = 9+4 (2 squares).

Algorithm Flow

Recommendation Algorithm Flow for Perfect Squares

Solution Approach

Find the minimum number of perfect square numbers that sum up to n. Use dynamic programming where dp[i] is the minimum squares for i. Initialize dp[0]=0 and all others to Infinity. For each i from 1 to n, try every square j*j <= i and take dp[i] = min(dp[i], dp[i - j*j] + 1).

function numSquares(n) {
  var dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (var i = 1; i <= n; i++) {
    for (var j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}

The recurrence considers each perfect square as the last coin in an amount-i coin change problem. For each square, we add 1 to the optimal solution for the remainder. The minimum across all squares is stored in dp[i].

Time complexity is O(n * sqrt(n)), space complexity is O(n).

Best Answers

java
class Solution {
    public int solution(int n) {
        int[] dp=new int[n+1];
        for (int i=0;i<=n;i++) dp[i]=i;
        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];
    }
}