How to get to the efficient solution of a problem on buying with exchange policy I was working through some coding challenges at hackerrank.com and got to this one.

I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. So I found this.

After explaining the naive method, which is the one that I used, then there is the efficient solution. But I can not understand the explanation that goes from the naive method to the efficient solution.

Can someone help me understand how is the logic to get to the efficient solution:


  In above naive implementation, we noticed that after finding initial number of chocolates, we recursively divide the number of chocolates with the number of wrappers required. until we left with 1 chocolate or wrapper.
  We are recomputing the values i.e. ((choc/wrap + choc%wrap)/wrap until we get 1.
  It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1)
It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1).


First, we can verify by brute force that the number of additional chocolates we can get by returning wrappers repeatedly is indeed (choc-1)/(wrap-1).

Second, here is how we can understand or prove that formula. 

Suppose we have wrap-1 wrappers. Imagine we can borrow one wrapper from a benefactor. Then we can return the wrap wrappers for a chocolate, the wrapper for which will be returned to the benefactor. So we do not owe the benefactor anything any more.

Looking back, we had wrap-1 wrappers initially while we had enjoyed one chocolate without wrapper in the end. So, every wrap-1 wrappers will bring one chocolate without wrapper, as long as we had no less than wrap wrappers. If we have choc wrappers, we will have choc/(wrap-1) wrapper-less chocolates. However, there is a catch. There is, in fact, no benefactor. So the number should be (choc-1)/(wrap-1) instead.

In a more friendly world where there are benefactors or a more admissible policy where wrap-1 wrappers can be exchanged for one wrapper-less chocolate, the number of additional wrapper-less chocolates will be choc/(wrap-1).