bytelandian coins doubt

bytelandian
c-plus-plus-14
coins
medium

#1

Can you tell me why this code is incorrect ?

#include iostream (*I have removed the brackets <>)
using namespace std;
int main()
{ int n,x,z; for(int i=1;i<=10;i++)
{cin>>n;
while(n>0) { x=(n/2)+(n/3)+(n/4);
z=max(x,n);
cout< < z;} } return 0; (*Actually no space between <<)
}


#2

Hello,

  1. The input format of the question is wrong. You have to keep taking the input until you have nothing to get. Solve the question named TEST to get familiar with the input style used here.
  2. You are making an infinite loop in while(n>0) because you are not changing the value of n inside the loop and checking if it is still greater than zero after each iteration.
  3. More coins can be made from the coins received after a conversion. Example : say we have 30 coins in the starting. We now convert them to 30/2 = 15 , 30/3 = 10 and 30/4 = 7 . Now to make a better sum, we can use the 15,10,7 coins again to change them into smaller denomination coins (like 15/2 etc).
  4. This is a basic problem of dynamic programming (or DP). Try googling what DP is why it is used here. DP is used here to optimise the code. A brute force (the most basic logic) would result in a “time limit exceeded” result.