How to prove f(n/a) + a < f(n/b) + b if a > b

  • 0

    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?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.