All problems

Perfect Squares

Medium · dynamic programming

A perfect square is a number you get by multiplying a whole number by itself: 1, 4, 9, 16, 25, ....

Given a positive integer n, write it as a sum of perfect squares. You may use the same square more than once. Return the smallest number of squares you need.

Examples

Example 1

Input: n = 12

Output: 3

12 = 4 + 4 + 4. No two squares add up to 12.

Example 2

Input: n = 13

Output: 2

13 = 4 + 9.

Example 3

Input: n = 16

Output: 1

16 is already a perfect square.

Constraints