Getting TLE for large cases

#1

Although used DP…but as it’s complexty is m*n hence near to 10^9…so need optimization…can u please sugest that

#2

@kaushikjatin try to make this question in of n time there is a possible solution in 0(n).

#3

bro…I couldn’t think of that solution I tried…can u give me just a little hint

that I could think in that way…

#4

Hey I know the space optimied approach…but r u really talking sbout the time optimised approach…because space optimization won’t help in TLE

#5

@kaushikjatin I’m saying about the time optimization.

#6

ya can u give me little hint …that in this way I must think…or hint relating to recuurence.

#7

@kaushikjatin just use one array and try to loop inside that array by adding the values of the coin changes. It would be better if you try to yourself.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#9

@amankumarkeshu bro r u talking about bottom-up approach i.e to use DP instead of Memoization?

#10

as you said for trying by DP…so I wrote this…but bro…I am getting wring answers…tried a lot…but couldn’t find mistake

#11

https://ide.geeksforgeeks.org/KO0Wc4Ig5H This is the link for my code…

#12

@kaushikjatin please use coding blocks ide for code Sharing. We are not allowed to check other ide codes

#13

@kaushikjatin Just use one loop for traversal and update your coin value simultaneously.

#14

Bro…don’t just feel bad but I think It’s just an excuse.I am also an TA but of Coding Ninjas…but I didn’t saw any such restriction in that process.I have shared the link…and just want to help you to go through the code once…please don’t mind the words…just go through the code…and help me find the mistake…And one more thing bro…I am pretty sure that this problem cannot be done in O(n) which u r saying…just look at the question again bro…in this code I did the space optimization also…but now just failing to get my code correct…And bro…I didn’t know how to generate link for the coding blocks ide…so I just share link of gfg code…

#15

@kaushikjatin This question can be done in 0(n ) time. I’ll send you the approach tomorrow as I open my laptop.

#16

@kaushikjatin Yeah no problem with the link I just asked you if it is possible then use coding blocks ide. Never mind.

#17

okkey bro…I will look forward to it…

#18

Hey @kaushikjatin
You opened this doubt
How can I help you ?

#19

I was getting TLE in 2 cases in the money change question…I used DP…I also shared y approach…but the TA said it is to be done in O(n) time complexity…I don’t have a idea of it and he just said to give me hint/code regarding that but he resolved my doubt…

#20

Hey @kaushikjatin
My fellow TA might have made an error
Sorry for that
In this ques N*M complexity is fine
I’m sending the code for N*M complexity here for you to cross verify