Exchanging Coins

#1

I m getting MLE upon submitting can someone tell if i m using any unneccesary space

#2

Hey @Vibhor_Saxena
Use an unordered map instead because you will not be using most of the space in dp array
say we have n then we go to n/2 , n/3 and n/4 so here we will not be using space from n/2+1 to n-1 ever.
So we don’t need most of the space and n can be as large as 1 000 000 000

#3

Hey,
I got why i was getting MLE and i corrected it but now the TCs are not passing
Can u please help me find what i m doing wrong

#4

Share ur code again :slight_smile:

#5

I made changes to that code only

#6

Hey @Vibhor_Saxena
Comment line 15 17 & 19

// if(n%2 == 0)
op1 = exchangedCoins(dp,n/2);
// if(n%3 == 0)
op2 = exchangedCoins(dp,n/3);
// if(n%4 == 0)
op3 = exchangedCoins(dp,n/4);

Not asked in the question.

#7

Hey thanks its passed, but i didn’t understand the reason why it was it was causing a error.
Like we can only change the coins to an integer value right, so if i m checking already that already before changing then why does it caused the output to be wrong, if u can just explain a bit

#8

For 16 ->16/2,16/3,16/4 ==8+5+4==17
So max value u can get from 16 is 17 here without going further but if you add those condition then op2 becomes 0 and not 5 and don’t give this answer

#9

Oh ok i got it
Actually i thought if that number is not divisible then we are allowed to change it.
Thank you

1 Like