1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.