Medium · Dynamic Programming

Perfect Squares

Given an integer n, return the least number of perfect squares (1, 4, 9, 16 and so on, each usable any number of times) that sum to n.

Examples

Example 1

n = 12

Output: 3 squares

Example 2

n = 7

Output: 4 squares

Rebuild it in the studio

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Dynamic Programming problems