Return the minimum number of perfect square numbers whose sum is exactly n.
Given a positive integer n, find the minimum number of perfect square numbers whose sum is exactly n.
A perfect square is an integer of the form k^2 where k is a positive integer.
Your task is to choose as few squares as possible while still summing to n.
n.n.1 <= nn.n.1 <= nExample 1
Input
n = 12
Output
3
Explanation
12 = 4 + 4 + 4, so the minimum count is 3.
Example 2
Input
n = 13
Output
2
Explanation
13 = 4 + 9, so the minimum count is 2.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.