Given a positive integer n, find the minimum number of perfect square numbers that sum to n. For example, n=12 can be written as 4+4+4 (three squares) or 9+1+1+1 (four squares). The answer is 3.
This is a dynamic programming problem, but logarithms appear when computing perfect squares. How many perfect squares are there up to n? About n, and log2(n)=21log2(n).
Before reading the solution, think about this: how would you find all perfect squares up to n? And how does the logarithm relate to the number of bits in n?