Number of ways to make coin change when change is larger (repetitions of coins are allowed and order does matter)
Difference between en3 and en4, changed 102 character(s)
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. Lang. By When Δ Comment
en4 English 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 English naveen_1729 2021-05-09 10:11:09 102 Reverted to en1
en2 English 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 English naveen_1729 2021-05-09 09:58:11 786 Initial revision (saved to drafts)