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] — > stores 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.
↵
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 <=
1 <= A[i] <= 10^2 (A[i] — > stores th
↵
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.
