Exchange gold coins
In a monetary system each coin has an integer number written on it. A coin 'n' can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down.
You can also sell coins for dollars and their exchange rate is 1:1.
You have one gold coin. What is the maximum amount of dollars you can get for it?
eg:
for a coin with value 120 you can get 144 dollars.Suggest an algorithm to solve the problem.
r u sure that for 120 value coin we can get 144 dollars??..I got only 88 dollars.
ReplyDelete@puppala for 120 couns you must be doing one level calculation so breaking down 120 you got 60+40+30 = 130 and breaking down 60 you get 30+20+15 = 65 and 30 as 15+10+7=32 and 40 as 20+13+10 = 43 and so on.. calculate it this way and you will get 144..this is a memorization problem where you solve a part of problem and store its result so that can use it for further...
ReplyDeleteI think it's a counting problem, so DP will be used.
ReplyDeletewe will start from 1 and move till N.
The recurrence will be :-
v[0]=0;
for(int i=1;i<=n;i++)
{
int sum=v[i/2]+v[i/3]+v[i/4];
if( sum < i)
v[i]=i;
else
v[i]=sum;
}
Navin it is solvable with 2 lines of code recursively.
ReplyDelete@Nader can you please post those two lines of code and its complexity. Don't forget to compare it with DP solution provided by Navin, that will help others to have better insight of solution to the problem.
ReplyDelete