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 <= W <= 10^9
1 <= A[i] <= 10^2 (A[i] — > stores the 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.
Matrix binary exponentiation can be used to get $$$O(A^3log(W))$$$ time complexity where A = 100. The original dp can be written as $$$dp[i] = \sum_{j = 1,100} x_{j}*dp[i-j]$$$ where $$$x_{j}$$$ = no. of coins with value j.