Command Palette

Search for a command to run...

Hectal
Problem 30.7 · Knapsack DPMedium

Perfect Squares

PatternKnapsack DPGraph BFS

What it teaches: Coin change where the coins are 1, 4, 9, 16, …

Practise it on judges as “Perfect Squares”.

The problem

Return the least number of perfect squares that sum to n.

Example 1

Input: n = 12
Output: 3

4 + 4 + 4.

Example 2

Input: n = 13
Output: 2

4 + 9.

Constraints

  • 1 ≤ n ≤ 10⁴

Pattern clues in the wording

  • → Fewest items to reach a sum

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int numSquares(int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 12
3
2
n = 13
2
3
n = 1
1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Unbounded min DP · O(n √n)
1

Unbounded min DP

Time O(n √n) Space O(n)

best[0] = 0; for each i, try every square j² ≤ i.

Approach 1
import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        int[] best = new int[n + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                best[i] = Math.min(best[i], best[i - j * j] + 1);
        return best[n];
    }
}

Verdict: Coin change with square coins.

Before you submit

Edge cases and common mistakes

Test these inputs

  • n is itself a square (1)
  • n = 1

Mistakes people make

  • Greedy largest square first (12 = 9 + 1 + 1 + 1 uses 4).

Interview

Follow-up questions

Is there a math shortcut?