Perfect Squares Sum

Find the minimum number of perfect squares that sum to a given integer.

dynamic-programming math optimization dp

Write a function `min_squares(n)` that takes a positive integer `n` and returns the minimum number of perfect square numbers (like 1, 4, 9, 16, ...) needed to sum up to `n`. You may use each perfect square any number of times.

The function signature is:
```python
def min_squares(n: int) -> int:
```

For example, `min_squares(12)` returns 3 because 12 = 4 + 4 + 4 (three 4s). `min_squares(13)` returns 2 because 13 = 9 + 4.

Implement the function efficiently. The expected time complexity is O(n * sqrt(n)) and space O(n).

Constraints

- 1 <= n <= 10^4
- The answer always exists (since 1 is a perfect square).
- Aim for O(n * sqrt(n)) time and O(n) space.

Example

>>> min_squares(1)
1
>>> min_squares(2)
2
>>> min_squares(4)
1
>>> min_squares(12)
3
>>> min_squares(13)
2

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of dynamic programming: dp[i] = minimum squares to sum to i.

For each i from 1 to n, try subtracting every square s where s <= i.

dp[i] = 1 + min(dp[i - s]) over all squares s <= i.

Initialize dp[0] = 0 and build up.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.