Perfect Squares Problem

Perfect Squares Problem — ExecCode Medium DSA Practice

Solve the Perfect Squares problem on ExecCode. Free online medium DSA practice in Math. Write and run code in Java, C++, Python — no signup required to run.

Problem 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 — for example 1, 4, 9, and 16. You may use the same perfect square more than once. Return the minimum count of such squares needed. For example, n = 12 can be written as 4 + 4 + 4 (three squares), which is better than 9 + 1 + 1 + 1 (four squares).

Examples

Input n = 12; Output 3. Input n = 13; Output 2. Input n = 1; Output 1

Constraints

1 ≤ n ≤ 10⁴

Practice Perfect Squares free on ExecCode. Browse DSA problems, topic map, and placement guides.