Medium

Quiz

#279 Perfect Squares

APPROACH

Given a positive integer n, return the minimum number of perfect square numbers that add up to n. A perfect square is any integer that equals some integer multiplied by itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12

Output: 3

Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

1 of 4

1:00

What is the optimal approach for this problem?