Exchanging coins-test case explanation

#1

plz explain one of the test cases

#2

Hello,
In this question you have consider three things:

  1. each coin has a number written on it.
  2. you can buy gold with a coin of amount(in kg) written on the coin.
  3. In exchange of your coin of value n, you can get three coins of values n/2, n/3, n/4 i.e. in total you would have a total amount of (int)(n/2) +(int)(n/3) +(int)(n/4)

Now, you have to calculate the max. amount(in kg) of gold you can buy, by the coin you are given initially.

Suppose, N=12
now you have two choices:

  1. do not exchange coin with bank, i.e total amount=12
  2. exchange n to (n/2,n/3,n/4) i.e. total amount=6+4+3=13

Now, you have to select max of both. here it is 13.
Recursively, you can break the coins further and than return the max of above two choices/amounts.
But, the parameter we are passing every time in function is an integer, so some values of n will repeat.

This satisfies two conditions of DP i.e. Optimal substructure and overlapping substructures.

In our case, the max. value of will come out to be 13.

Hint:
From the problem definition, say a function, f (n) return ways to compute the change.

recursive statement/calls:
f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4)) // here recursion is taking place.
Base case:
f (0) = 0
f(1) =1

Hope, this would help.
if you still have doubts, feel free to ask.

10 Likes
#3

Thank u,the question is now clear to me…awesome explanation

#4

you can give a like, i won’t mind.:wink:

3 Likes