The solution of this question seems pretty simple, most of them are based of this assumption:
- define f(n) as the number of operation we need to do to get n As. f(n) = f(n/a) + a
the best solution could be found by finding the smallest factor of n, a, recursively.
While this seems very straight forward, no one seems to prove that is correct mathematically or prove this:
- for given N, if there're two different factors a, b and a<b, then f(N/a) + a > f(N/b) + b
I don't think we can assume this correct because N/a >N/b, a<b and f(n) is not a monotonic function.
What do you guys think?