Bytelandian gold coins

getting wrong answer…
my code is
#include<stdio.h>
int main()
{
unsigned long n,p;

while((scanf("%lu",&n))!=EOF)
{
p=0;
if(n<12)
printf("%lu",n);
else
{
p=(n>>1)+(n/3)+(n>>2);
if(p>n)
printf("%lu",p);
else
printf("%lu",n);
}
}
return 0;
}

2 Likes

your solution have wrong assumption about the problem…you have used

p=(n>>1)+(n/3)+(n>>2)
which is not right.if you define a function fun(x) then
fun(x)=fun(x/2)+fun(x/3)+fun(x/4)
for example let us we calculate for n=36 the its n/2=18 and n/3=12 and n/4=9.

since he can exchange 12 to 13$ and for 18 to 19$ and 9 to 9$ therefore you can exchange 36 with 13+19+9=41$ which will be right answer but according to your solution it will be 12+18+9=39$ which is wrong.
therefore we have to do the problem by Dynamic Programming by precalculating all the values then output according to queries.or another way to make a recursive solution with memoization.

7 Likes

Hi Ajay,

How to use memorization technique here. What kind of data structure we are going to use for storing the result of the sub problem. I think array will not work here as dimension will be very big.

You can use a map to memo the data. Then you can easily get the answer using recursion.

1 Like