Loading problem...
Given a positive integer n, determine the minimum count of perfect square numbers required to sum up to exactly n.
A perfect square is a number that can be expressed as the product of an integer with itself. For instance, 1 (1×1), 4 (2×2), 9 (3×3), 16 (4×4), and 25 (5×5) are all perfect squares. Numbers such as 2, 7, or 11 are not perfect squares since they cannot be expressed as a square of any integer.
Your task is to find the optimal decomposition of n into a sum of perfect squares, minimizing the total count of terms used. Note that the same perfect square can be used multiple times in the decomposition.
Mathematical Foundation: This problem is related to Lagrange's Four Square Theorem, which states that every positive integer can be represented as a sum of at most four perfect squares. However, many numbers can be expressed using fewer squares. Your algorithm should find this minimum count efficiently.
n = 123The number 12 can be decomposed as 4 + 4 + 4 (using three perfect squares of 2²). While other decompositions exist (like 9 + 1 + 1 + 1, which uses four squares), this is the minimum possible.
n = 132The number 13 can be decomposed as 9 + 4 (using 3² + 2²). This uses only two perfect squares, which is the minimum for 13.
n = 161The number 16 is itself a perfect square (4²), so it can be represented using just one perfect square.
Constraints