Number of ways of coin exchange

#1

code–>


question–>
https://practice.geeksforgeeks.org/problems/coin-change2448/1#
the recursive case is not giving correct answer help

#2

this problem is not minimum coin problem right

#3

Actually this problem is that how many ways can we make the change of a given amount with array of coins. I can see there’s no dp table too. You might have misunderstood this question?

#4

yes i taught this was that basic minimum coin exchange problem , okay i will try that problem if any trouble i will ping you

#5

Sure, just let me know if you need any assistance.

#6

question–>
https://practice.geeksforgeeks.org/problems/number-of-coins1824/1#
code–>


it is not passing all testacses help !!

#7

Here’s the code i have implemented using your fun function, your implementation for fun function was sufficient.
Complexity for this program is of course O(n)

#8

bro that fun (function ) takes o(k^amount) complexity right? help me to correct the fun3 function, i cannot understand the above code what u have done?

#9

Logic is not correct in this as we have to count the total number of solutions, we can divide all set solutions into two sets.

  1. Solutions that do not contain mth coin (or Sm).
  2. Solutions that contain at least one Sm.
    Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems. So this for loop is doing the same

for(int i=0;i<m;i++){
	        for(int j=S[i]; j<=n; j++) 
            table[j] += table[j-S[i]]; 
	    }

Still have an issue, feel free to ask

#10

it got submitted


but the time complexity is O(amount*coins.length())
not o(n) i think

#11

bro i am asking about the minimum coin exchange problem not this

#12

arey shit, woh galat problem ka link diya na toh isliye confusion ho gyi

#13

tumahra accept ho gya na solution?

#14

haa just thoda test cases according change kiya toh ho gya

#15

Chlo bdiya, marking it as resolved.

#16

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.