The solution is attained using dynamic programming. The basic idea is that the minimum number of stamps used for attaining an amount x, is 1+minimum of (minimum number of stamps for attaining x-5, minimum number of stamps for attaining x-10, minimum number of stamps for attaining x-20,minimum number of stamps for attaining x-50). You can try to solve this first by assuming that an unlimited number of 5 rupee, 10 rupee, 20 rupee and 50 rupee stamps are available. And then you can take into account that only a fixed number of these stamps are available.

And what is the time involved to get this done? I really liked the question.Simple to read but involves good amount of logic. I ve written down the algorithm but i believe i took more time than i initially thought i would take.

I understand what the interviewer is trying to test and I know how to solve it, but what about more realistic scenario where parcel postage cost would be beyond given values like 3 units of currency or 37 units of currency.

In this specific case, dynamic programming is overkill. There's a better optimal substructure here: The stamp with greatest value less than parcel cost minus stamp values already committed minimize the total of stamps.

1. find the stamp <= cost from highest stamp cost 2. num of found_stamp = found_stamp/cost, rem_stamp = found_stamp % cost 3. Do 1, then 2 until rem_stamp ==0 (done) or rem_stamp < least stamp available (not possible case)

In the previous ans, after step 3 if rem_stamp !=0, go back to step 1, find next_stamp < cost (but smaller than value of found_stamp in previous iteration)

i=0; boolean solPossible = false; do { if(cost % notes[i] == 0) solPossible = true; else i++; } while(!solPossible && (i

void sendParsal(int cost) { int[] avlstm={50,20,10,5}; int i=0; while(cost>=5) { while(cost>=avlstm[i]) { System.out.println(avlstm[i]); cost=cost-avlstm[i]; } i++; } if(cost!=0) { System.out.println("Solution not possible."); } }