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
Recommendation Algorithm Flow for Perfect Squares

Solution Approach

DP: dp[i] = min(dp[i], dp[i - j*j] + 1) for all j*j <= i. Initialize dp[i] = i.

function solution(n) {
  var dp = new Array(n + 1);
  for (var i = 0; i <= n; i++) dp[i] = i;
  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];
}

Time O(n*sqrt(n)), Space 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];
    }
}