Description
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 (1, 4, 9, 16, ...).
Examples
Input:
n = 12Output:
3Explanation:
12 = 4 + 4 + 4.
Input:
n = 13Output:
2Explanation:
13 = 4 + 9.
Input:
n = 18Output:
2Explanation:
18 = 9 + 9. It is possible to represent 18 as the sum of two perfect squares (3² + 3²), which is optimal since 18 cannot be expressed as a single perfect square.
Constraints
- •
1 ≤ n ≤ 10⁴