## Saturday, May 10, 2014

### Problem

Assumptions:
a) I have infinite money in my account
b) The daily limit of amount of money that can be withdrawn from an ATM is finite
c) You can login into an ATM Machine only once a day
d) If you login into the machine and enter a large number to withdraw, you will not get anything. And hence, you will not be able to withdraw anything from the ATM for the day.
e) I do not know what the daily limit is.

What strategy should I choose so that I can withdraw N rupees in minimum number of days?

### Solution

Of course, you can do it in N days (withdrawing only one rupee daily)
you could do it in N-limit + ceiling(N/limit)-1 days (check N, check N-1, .. check limit. Once you know the limit, and you have already withdrawn 'limit' rupees, you will take ceiling ((N-limit)/limit) days more.

Another approach can be first day we go and withdraw Re 1, and then Rs 2, 4, 8 and so on. The day will come when we will not be able to withdraw the money. Note that you can do it for (log limit +1) days. By that time you would have accumulated (2^M-1) rupees(using Geometric progression sum).
For the remaining rupees N-2^limit + 1, draw at the rate last accepted by the ATM. So, we will have log (limit ) +1 + (N - (2^M-1))/limit