Follow @trinisoftinc

A friend of mine have a saying

**Even if you will never write a line a code in your LIFETIME, learn how to program so that your LIFETIME can be easier.**

I confirmed this saying today when another friend gave us a problem, according to him most people got it wrong, but all the programmers got it right. It is a very simple real life problem

**The problem:**

A shop sells candies for 10 NGN each. You can exchange 3 candy wrappers for 1 candy. If you have 150NGN, how many candies can you totally get.

**Manual Solution:**

First how many candies can you get with 150NGN. 15candies, so we start from 15 candies. 3 candies or 3 candy wrappers are the same, since you can’t steal candy wrappers from your friends, so 15 candies will give you an additional 5 candies when you exchange the wrappers for candies. But your 5 candies are also eligible for the candy wrappers promo, therefore your 5 candies will give you an additional 1 candy and you will have 2 candies (or 2 candy wrappers) left. In total you now have 3 candy wrappers. These last three can give you 1 more candy and then you can’t have more candies because you are left with only one candy wrapper.

Going back from above, you now have 15 + 5 + 1 + 1 candies = 22 candies. You can have 22 candies from 150NGN.

**Automated Solution:**

I will assume that you know your multiplication tables very well, therefore you know how many candies you can get for the X amount of NGN that you have. So starting from N candies

- Lets define Q as number of candies / 3 (Quotient after division)
- Lets define R as number of candies % 3 (Remainder after division)
- At every point in time, the number of candies you have is Q + R, NOC = Q + R.
- Lets define ACC as the accumulated number of candies you have, in the above ACC = 15, ACC = 20, ACC = 21, ACC = 22.
- Starting from Q = 15, and R = 0 and ACC = 0 we can have the below procedure

- NOC = Q + R
- if NOC < 3, ANSWER=ACC
- if ACC = 0, ACC = NOC
- Q = NOC / 3
- R = NOC % 3
- ACC = ACC + Q
- ANSWER = back_to_step(i)

In step 7, we recursively call the procedure again until we get an answer. So Starting at Q = 15, R = 0, ACC = 0

NOC = 15 + 0 = 15 NOC > 3, noACtion ACC = 0, ACC = 15 Q = 15 / 3 = 5 R = 15 % 3 = 0 ACC = 15 + 5 = 20 ANSWER = NOC = 5 + 0 = 5 NOC > 3, noAction ACC != 0, noAction Q = 5 / 3 = 1 R = 5 / 3 = 2 ACC = 20 + 1 = 21 ANSWER = NOC = 1 + 2 = 3 NOC = 3, noAction ACC != 0, noAction Q = 3 / 3 = 1 R = 3 / 3 = 0 ACC = 21 + 1 = 22 ANSWER = NOC = 1 + 0 = 1 NOC = 1, ANSWER = 22

ANSWER = 22.

The beautiful thing is the automated solution can now be used to solve for ANY amount of initial candies. To complete this post, I will post the python script that I used to solve it.

Follow @trinisoftincdef hmc(q, r, acc): noc = q + r if(noc < 3): return acc if(acc == 0): acc = noc newQ = noc / 3 newR = noc % 3 acc = acc + newQ return hmc(newQ, newR, acc)