Question

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Answer 1

Answer:

Input: n = 100

Output: 1

100 can be written as 102. Note that 100 can also be

written as 52 + 52 + 52 + 52, but this

representation requires 4 squares.

Input: n = 6

Output: 3