This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:
"When a candle finishes burning it leaves a leftover.
m leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.
c candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?"
So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.
Now, I solved this with a while loop, and the loop itself just involves division and modulo math:
def candles(c, m): burned=c while c>=m: burned+=c//m c=(c%m)+c//m return burned
But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:
return c + (c - 1) // (m - 1)
I was hoping someone could help me figure out what techniques are used to arrive at this solution.