Perfect Squares

The key idea

The fewest squares summing to i is one more than the best you can do for some smaller target i - s, where s is a perfect square <= i: dp[i] = 1 + min(dp[i - s]) over every square s. Each value i is built from an already-solved smaller value, so a single left-to-right pass fills the whole table.

Problem

Given a positive 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.

Constraints

1 <= n <= 10^4

Examples

Input: n = 12 Output: 3

Input: n = 13 Output: 2

Complexity

Time: O(n * sqrt(n)) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →