Number of ways to make coin change when change is larger (repetitions of coins are allowed and order does matter)
Разница между en3 и en4, 102 символ(ов) изменены
Hi Fellow Coders, ↵

Hope you are all doing good. This is my first blog.↵
Today I gave Hackwithinfy test. I got asked a question similar to the standard DP problem which is **Count the number of ways to make the change (repetitions of coins are allowed and order does matter)**. I know this problem can be solved in Quadratic time 


O(N * W)    ↵

W — > Required Change↵

N — > Number of coins↵

But the constraints given in the problem are huge↵

1 <= N <= 10^5↵

1 <= XW <= 10^9↵
I was so su
1 <= A[i] <= 10^2 (A[i] &mdash; > sto
res this would give me a TLE at the time.e value of the coin)↵

I was so sure this would give me a TLE. But,
 I couldn't come up with a better approach than the standard one. I wonder if there is a better approach that would have given me an AC. 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский naveen_1729 2021-05-09 10:11:33 102 Tiny change: 'atic time O(N * W) \nW &mdash' -> 'atic time \n\nO(N * W) \n\nW &mdash' (published)
en3 Английский naveen_1729 2021-05-09 10:11:09 102 Reverted to en1
en2 Английский naveen_1729 2021-05-09 10:08:48 102 Tiny change: 'atic time O(N * W) \nW &mdash' -> 'atic time \n\nO(N * W) \n\nW &mdash'
en1 Английский naveen_1729 2021-05-09 09:58:11 786 Initial revision (saved to drafts)