You are viewing a single comment's thread. Return to all comments →
This approach is clean and easy to follow, which is great.
However, it results in O(N) time (input of 10000 1 2 results in the loop running 9999 times.)
If you switch the loop to the following you end up with O( lg(N)) (or 14 in the worst case, since you are using integer math).
def chocolateFeast(cash, cost, wrapper_cost): chocolate = cash//cost wrappers = chocolate while wrappers // wrapper_cost > 0: new_chocolate = wrappers // wrapper_cost wrappers -= new_chocolate * wrapper_cost wrappers += new_chocolate chocolate += new_chocolate return chocolate
Chocolate Feast
You are viewing a single comment's thread. Return to all comments →
This approach is clean and easy to follow, which is great.
However, it results in O(N) time (input of 10000 1 2 results in the loop running 9999 times.)
If you switch the loop to the following you end up with O( lg(N)) (or 14 in the worst case, since you are using integer math).