Perfect Squares

You are given an 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. For example, 1, 4, 9, 16, 25... are perfect squares.

Example 1:

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

Example 2:

Input: n = 6

Output: 3

Explanation: 6 = 4 + 1 + 1.

Constraints:

• 1 <= n <= 10,000