We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  1. Practice
  2. Algorithms
  3. Dynamic Programming
  4. The Coin Change Problem
  5. Discussions

The Coin Change Problem

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

Sort 391 Discussions, By:

votes
  • recency
  • votes

Please Login in order to post a comment

  • jppkid 4 years ago+ 40 comments

    watch out for integer overflow :). i had to switch to 64-bit int.

    135|
    Permalink
    • AlphaBeta55 4 years ago+ 2 comments

      Thank you

      0|
      ParentPermalink
      • hargar 2 years ago+ 1 comment
        [deleted]
        -22|
        ParentPermalink
        • hargar 2 years ago+ 1 comment
          [deleted]
          -16|
          ParentPermalink
          • hargar 2 years ago+ 0 comments
            [deleted]
            -22|
            ParentPermalink
      • abhaykuma 7 months ago+ 1 comment
        long getWays(long n, vector<long> c) {int64_t A[c.size()][n+1];
            for(int64_t i=0;i<c.size();i++){A[i][0]=1;}
            for(int64_t i=0;i<c.size();i++)
            {for(int64_t j=1;j<=n;j++)
            { int64_t x,y;
             x=(i>0) ? A[i-1][j]:0;
              y=(j-c[i]>=0)? A[i][j-c[i]]:0;
            A[i][j]=x+y;    
            }}
            
          return A[c.size()-1][n];}
        

        what is wrong with this

        0|
        ParentPermalink
        • sxy1573 4 months ago+ 1 comment

          My method is same to you,l also get wrong . But my debug answer is same to the true answer.

          6|
          ParentPermalink
          • sauravjack 4 months ago+ 1 comment

            same is happening with me.

            0|
            ParentPermalink
            • priyankajiandani 4 months ago+ 1 comment

              same problem I am getting

              1|
              ParentPermalink
              • mohitsnh6 4 months ago+ 1 comment

                Please add fout << ways; just before closing it in the main function i.e just before fout.close() I don't know why it is not already included.

                0|
                ParentPermalink
                • MT2018016 3 months ago+ 0 comments

                  For Java Users: In the Main function "ways" is not written to the file. Add bufferedWriter.write(String.valueOf(ways)); in the main function.

                  11|
                  ParentPermalink
    • tashia 4 years ago+ 2 comments

      Thank you !

      -13|
      ParentPermalink
      • hargar 2 years ago+ 0 comments

        thanks

        -8|
        ParentPermalink
      • kumar_malay888 2 years ago+ 1 comment

        this is my code and used java8 :- for coin change problem

        public static String CoinChange(int input1,int[] input2) { return CoinChange(input1,input2,0,new HashMap()); }

        public static String CoinChange(int input1,int[] input2,int a, HashMap<String,Long> memo)
        {
            int b = 1;
            int c = 0;
            long d = 0;
            String x = "";
            if(input1 == 0)
            {
                return (x = String.valueOf(b));
            }
            if(a >= input2.length)
            {
                return (x = String.valueOf(c));
            }
        
            String z = input1+"-"+a;
        
            if(memo.containsKey(z))
            {
               d = memo.get(z);
               return (x = String.valueOf(d));
            }
            int e = 0;
            long f = 0;
        
            while(e <= input1)
            {
                int g = input1 - e;
                f += CoinChange(input2, g, a+1,memo);
                e += input2[a];
            }
            memo.put(z,f);
            return(x = String.valueOf(f));
        
        
            and i was getting a error which is
            CandidateCode.java:43: error: incompatible types: int[] cannot be converted to int
                f += CoinChange(input2, g, a+1,memo);
        
        
                can anyone please solve this
        
        -15|
        ParentPermalink
        • iybaron25 1 year ago+ 0 comments

          The first argument for your method "CoinChange" takes an int. You are passing it "input2" which is an int array.

          1|
          ParentPermalink
    • acodebreaker 4 years ago+ 2 comments

      thanks

      -23|
      ParentPermalink
      • Dream_machine 4 years ago+ 1 comment

        thanks :)

        -11|
        ParentPermalink
        • hargar 2 years ago+ 1 comment

          thanks

          -14|
          ParentPermalink
          • phuadc123 2 years ago+ 1 comment

            thanks

            -6|
            ParentPermalink
            • mohitduklan 1 year ago+ 1 comment

              thanks

              -11|
              ParentPermalink
              • naveenkrjr7 9 months ago+ 0 comments

                thanks :p

                -1|
                ParentPermalink
      • amazinghacker 3 years ago+ 4 comments

        Do we have to use recursion with dynamic programming to solve this?

        -21|
        ParentPermalink
        • dipu11 3 years ago+ 0 comments
          [deleted]
          -7|
          ParentPermalink
        • robbyoconnor 3 years ago+ 1 comment

          dynamic programming is really just caching previous work

          17|
          ParentPermalink
          • oubenal 1 year ago+ 1 comment

            Memoization*

            -1|
            ParentPermalink
            • naveenkrjr7 9 months ago+ 0 comments

              Tabulation

              0|
              ParentPermalink
        • piyusman 3 years ago+ 5 comments

          public static long count(long sum,long[] coins , int coin_num){

                 if(sum==0){
          
                     return 1;
          
                 } 
                  else if(sum<0){
                      return 0;
                  }
                  else if(coin_num<=0){
                      return 0;
                  }
                  else if(memo[(int)sum][coin_num]!=-1){
                       return memo[(int)sum][coin_num];
                 }
          
                  else{
                  memo[(int)sum][coin_num]=count(sum,coins,coin_num-1)+count(sum-coins[coin_num-1],coins,coin_num);
                 return memo[(int)sum][coin_num];
              }
             }
          

          Here we are caching the previous result in memo multidimensional array. First you need to initialize it wih some number(you can use Arrays.fill for that) Also I tried to make it clear what memo is really doing. Means if the ways for particular sum is already there then no need to calulate again. Else go ahead and solve.

          sum = amount

          coins = array of all available coins.

          coin_num is length of coins array(or you can say that next int in first line of this question's input)

          So basically if you have

          sum = 100;

          coins[] = {25,10,5,1};

          coin_num = 4;

          memo[][] = new long[sum+1][coin_num+1];

          and then call countWays(sum,coins,coin_num);

          I have a question to others though, in java when I am trying to make it long I have to do a lot of casting, any other way to deal with the 'long' problem.

          -10|
          ParentPermalink
          • sushant001 3 years ago+ 1 comment

            Your comment helped, so here goes mine ... Rather than using 2D array, create another class (Let call it Change having long sum, int coin . override equals and hashcode- hashcode is really important , use hashcode = sum, that will be good enough ).

            Now , in place of 2D array, use map (HashMap). and you are done.

            Thanks

            0|
            ParentPermalink
            • andadeacu 1 year ago+ 0 comments

              What can store in HashMap? For example: fot the first example: HashMap would contain (1,4), (1,2), (2,1) (2,2) (1,3)

              0|
              ParentPermalink
          • bnegrao 2 years ago+ 4 comments

            I don't understand why if sum == 0 then return 1; If sum is 0 and the coin values are >= 1, how can I have one solution if the sum is 0? if sum is 0 I should have 0 solutions...

            0|
            ParentPermalink
            • qwerjoe 2 years ago+ 0 comments

              if your sum == 0 then you have already found a 'valid' variation of coins in the previous level of the recursion.

              And if N = 0, the output should be 1 (zero from every coin type is the 1 and only good solution here)

              2|
              ParentPermalink
            • mk9440 2 years ago+ 0 comments

              it is just as factorial of zero = 1 ie no of ways.

              4|
              ParentPermalink
            • abhidash 1 year ago+ 0 comments

              Because one valid solution is to not use any coin at all.

              0|
              ParentPermalink
            • dewscoder 1 year ago+ 0 comments

              when sum is zero, a valid selection of coins would be null set i.e., {}, and thats why return 1

              -2|
              ParentPermalink
          • jiwan_chung 2 years ago+ 2 comments

            I didn't understand

            count(sum,coins,coin_num-1)+count(sum-coins[coin_num-1],coins,coin_num);

            part, can anyone explain me kindly? I really want to understand DP... :(

            0|
            ParentPermalink
            • sumeet_ram 2 years ago+ 3 comments

              Its like, what you do for, finding the number of subsets of a set. Whether an element belongs to your set or it doesn't.

              Here, either you use the last coin (in your set of given coins) to make change or you dont.

              In case you dont use the last (say 'm'th) coin, now you are left with the subproblem of solving the toatal amount('sum' variable here) using onle the remaining 'm-1' coins ([0:m-2] in the array). We cant use the 'm'th coin because by our own assumption, its not part of the subproblem.

              In case you use the last coin, you have the subproblem of solving "sum-Value('m'th coin)" using all the 'm' coins ( because using the 'm' th coin once doesnt bar you from using it again).

              Finally you can add the count from both the cases as either of them are a possibility in your final solution.

              Lemme know if this helped!!

              10|
              ParentPermalink
              • Snigdha_Sanat 1 year ago+ 1 comment

                @sumeet_ram I did not understand it still, can u please elaborate it a bit more? The choice of the 2 subproblems(count(sum,coins,coin_num-1) and count(sum-coins[coin_num-1],coins,coin_num)) do not look intuitive to me- what am I missing?

                0|
                ParentPermalink
                • midnjerry 1 year ago+ 4 comments

                  Imagine it like a tree....

                  let's say we have n = 25 and c = [1,2,3]

                  we can break it down from 25 into 3 branches by:

                  25 = 1 + f(24)

                  25 = 2 + f(23)

                  25 = 3 + f(22)

                  each of these scenarios also branch off:

                  f(24) = 1 + f(23)

                  f(24) = 2 + f(22)

                  f(24) = 3 + f(21)

                  f(23) = 1 + f(22)

                  f(23) = 2 + f(21)

                  f(23) = 3 + f(20)

                  f(22) = 1 + f(21)

                  f(22) = 2 + f(20)

                  f(22) = 3 + f(19)

                  As you keep on propagating... all of the permutations that end up negative are invalid combinations. all of the permutations that end up exactly at 0 are good combinations.

                  this is a simplistic approach but it's not correct. Because it doesn't differentiate between... [2,2,5] and [5,2,2]. To get only unique combinations you need to remove 1 element from the C set everytime you iterate.

                  so... it'll look like this (in pseudo code).

                  static long getWays(long n, long[] c) {
                  		if (n < 0) {
                  			return 0;
                  		}
                  		if (n == 0) {
                  			return 1;
                  		}
                  		if (CacheValuePopulated(n)){
                          return CacheValue(n);
                          }
                          
                  		long sum = 0;
                  		for (int i = 0; i < c.length; i++) {
                  			long target = n - c[i];
                  			long[] subc = subArrayOfCFrom(i to end);
                  			long result = getWays(target, subc);
                  			if (result > 0) {
                  				saveResultToYourCache(result);
                  			}
                  			sum += result;
                  		}
                  		return sum;
                  	}
                  
                  Finally... what made the cache problematic was that you can't just save values for any given n.  You have to save values for n BASED on the C subArray you used to calculate it.
                  

                  Since the problem states that all values of c are unique, I used the first element of the c subarray as a key which pointed to its own n+1 array.

                  So for example, the cache could differentiate between running (5, [1,2,3]) and (5, [2,3])

                  f(5,[1,2,3]) = 4 (1,1,1,1,1), (1,1,1,2), (1,1,3), (2, 3) f(5,[2,3]) = 1 (2,3)

                  I hope this helps everyone. I didn't want to give the full answer away. Good luck!

                  26|
                  ParentPermalink
                  • ErikWitkowski 1 year ago+ 1 comment

                    but if you remove the element you just use you cannot have repeated elements like [2,2,5], can you?

                    1|
                    ParentPermalink
                    • fzy1995 1 year ago+ 0 comments

                      he didn't remove the element he just used. read again. he's referring to start from i to end, which means it includes the index of the element he just used.

                      0|
                      ParentPermalink
                  • malviyan_shiv 12 months ago+ 0 comments

                    Couldn't got how to solve saving to cache problem ?

                    0|
                    ParentPermalink
                  • philip_cori 3 months ago+ 0 comments

                    Most helpful comment in this thread.

                    0|
                    ParentPermalink
                  • MinhThai2 2 months ago+ 0 comments

                    I tried using the strategy above but had no sucess due to overlap problem

                    Then i tried resolving it using knapsack strategy and it worked.

                    Excel containing the pattern: https://imgur.com/a/qzbDG5S

                    Solution passed all cases

                    0|
                    ParentPermalink
              • sasuke29 1 year ago+ 0 comments

                Thank you so much for your explanation :)

                0|
                ParentPermalink
              • santhos_kumar 1 year ago+ 0 comments

                Greatly  helped. Thankyou!

                0|
                ParentPermalink
            • munnusingh 9 months ago+ 0 comments

              While including the current coin as a part of solution why we are recurring it to count(sum-coins[coin_num-1],coins,coin_num). Should not it be count(sum-coins[coin_num],coins,coin_num)? Because, we coin_num is our current coint i.e. mth coin.

              0|
              ParentPermalink
          • munnusingh 9 months ago+ 1 comment

            While including the current coin as a part of solution why we are recurring it to count(sum-coins[coin_num-1],coins,coin_num). Should not it be count(sum-coins[coin_num],coins,coin_num)? Because, we coin_num is our current coint i.e. mth coin.

            0|
            ParentPermalink
            • ljason2020 8 months ago+ 0 comments

              As I understand it, the variable coin_num begins counting at 1. So coin number 1 would be the first coin in the array, which is actually index 0, hence you must subtract 1 from coin_num. It just depends on how you define the variable. You could use count(sum-coins[coin_num],coins,coin_num), as long as it fits with the rest of your program.

              0|
              ParentPermalink
          • dheerajkr2313 5 months ago+ 0 comments
            [deleted]
            0|
            ParentPermalink
        • InfinityRedux 12 months ago+ 1 comment

          There is a way of solving this without using recursion at all, just using dynamic programming. Instead of starting with "we want the solution for n" you can instead start with "what can we do with these coins".

          1|
          ParentPermalink
          • ljason2020 8 months ago+ 0 comments

            Yes, that is correct, but I believe you can do dynamic programming both recursively and iteratively (as you stated). The key aspect of dynamic programming is memoization or tabulation.

            0|
            ParentPermalink
    • meaaow 4 years ago+ 1 comment

      THANKS! :D

      -7|
      ParentPermalink
      • footstep 3 years ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
    • ABcdexter19 4 years ago+ 7 comments

      Did it in python 8-)

      2|
      ParentPermalink
      • Anachor 4 years ago+ 8 comments

        For a moment I was thinking- "What is python 8?"

        239|
        ParentPermalink
        • crazzy7 3 years ago+ 1 comment

          Me too

          0|
          ParentPermalink
          • agodfrey3 2 years ago+ 1 comment

            same

            0|
            ParentPermalink
            • agarwal_sumedha1 1 year ago+ 0 comments

              it is not passing the test case even if the expected value is same as the output

              13|
              ParentPermalink
        • maximshen 3 years ago+ 1 comment

          maybe python 3 or java 8 ?

          -74|
          ParentPermalink
          • ASHWIN_18 2 years ago+ 0 comments

            haha this is hilarious XD

            -1|
            ParentPermalink
        • gsnanda 3 years ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
        • Coder_BPPIMT 2 years ago+ 0 comments

          Same here

          0|
          ParentPermalink
        • anhthong_381996 2 years ago+ 1 comment

          it's "8-)" which is a smile face and isn't "python 8".

          -17|
          ParentPermalink
          • hargar 2 years ago+ 0 comments

            th@nks {@ is a not at}

            13|
            ParentPermalink
        • srivastava_ambi1 2 years ago+ 0 comments

          python and then [8-)] -> smiley

          -7|
          ParentPermalink
        • Akhil_yadav 2 years ago+ 0 comments

          it's python3

          0|
          ParentPermalink
        • harpz_ 12 months ago+ 0 comments

          lol.. me too :|

          0|
          ParentPermalink
      • amazinghacker 3 years ago+ 0 comments
        [deleted]
        -1|
        ParentPermalink
      • anhthong_381996 2 years ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
      • frandelarraniaga 1 year ago+ 0 comments
        [deleted]
        -1|
        ParentPermalink
      • Dularish 7 months ago+ 1 comment

        Can't seem to figure out the problem. It gives correct output on running in my IDE.

        #!/bin/python3
        
        import math
        import os
        import random
        import re
        import sys
        
        # Complete the getWays function below.
        memoizing_dict = {}
        
        # Complete the getWays function below.
        def getWays(n, c):
            global memoizing_dict
            if n < 0:
                return 0
            elif n == 0:
                return 1
            elif (n,len(c)) in memoizing_dict.keys():
                return memoizing_dict[(n,len(c))]
            else:
                cum_sum = 0
                for c_index in range(len(c)):
                    c_item = c[c_index]
                    if c_item > n:
                        continue
                    else:
                        result = getWays(n-c_item, c[c_index:])
                        if result > 0:
                            cum_sum += result
                memoizing_dict[(n,len(c))] = cum_sum
                return cum_sum
            
        
        if __name__ == '__main__':
            fptr = open(os.environ['OUTPUT_PATH'], 'w')
        
            nm = input().split()
        
            n = int(nm[0])
        
            m = int(nm[1])
        
            c = list(map(int, input().rstrip().split()))
        
            # Print the number of ways of making change for 'n' units using coins having the values given by 'c'
            
            ways = getWays(n, c)
            print(ways)
            fptr.close()
        
        1|
        ParentPermalink
        • CamJohnson26 7 months ago+ 3 comments

          The example program is broken, change print(ways) to fptr.write(str(ways))

          5|
          ParentPermalink
          • imdeepmind 7 months ago+ 0 comments

            Thanks man you just saved my life

            0|
            ParentPermalink
          • sauravjack 4 months ago+ 1 comment

            Thanks Bro!!!

            0|
            ParentPermalink
            • lucagiac 4 months ago+ 0 comments
              [deleted]
              0|
              ParentPermalink
          • lucagiac 4 months ago+ 0 comments

            Thank you so much for pointing that out. For Java, I added this line in the main method (right after the call to getWays).

            bufferedWriter.write(Long.toString(ways));

            0|
            ParentPermalink
      • shubham10dulkar1 7 months ago+ 2 comments

        def getWays(n, c):

        l=len(c)
        ways=[[0 for p in range(n+1) ] for m in range(l)]
        
        for p in range(0,l):
            ways[p][0]=1
        
        for p in range(0,n+1,c[0]):
            #print(p)
            ways[0][p] = 1
        
        for i in range(1,l):
            for j in range(1,n+1):
                p=j-c[i]
                if p <0:
                    x=0
                else:    
                    x=ways[i][p]
                y=ways[i-1][j]
                ways[i][j]= x+y
        print(long(ways[l-1][n]))
        

        i m getting expected output still test case not passing

        for example

        input:

        10 4

        2 5 3 6

        expected output: 5

        debug output : 5

        still test case fails

        plzz help

        1|
        ParentPermalink
        • jamesjosephclar1 7 months ago+ 1 comment

          I'm getting the same problem with Python 3. Doesn't matter what I try to change the output, nothing works.

          0|
          ParentPermalink
          • Dularish 7 months ago+ 2 comments

            You have to write to file pointer in the main

            4|
            ParentPermalink
            • jamesjosephclar1 7 months ago+ 0 comments

              Thank you, didn't realise this. Fixed my problem immediately.

              0|
              ParentPermalink
            • 7da46svqgw 6 months ago+ 0 comments

              What do you mean? I can't figure out what to do here

              0|
              ParentPermalink
        • prudvhvi 4 weeks ago+ 0 comments

          plz return dont print

          0|
          ParentPermalink
      • t_newman_uk 6 months ago+ 0 comments

        You, sir, are living in 2088

        0|
        ParentPermalink
    • trancekid 3 years ago+ 1 comment

      thanks :P

      -6|
      ParentPermalink
      • amazinghacker 3 years ago+ 0 comments
        [deleted]
        -1|
        ParentPermalink
    • subwaymatch 3 years ago+ 0 comments

      Another thanks.

      -9|
      ParentPermalink
    • dramforever 3 years ago+ 0 comments

      Can't thank you more...Just got wrong answer for a few test cases and saw your comment

      -7|
      ParentPermalink
    • ajcoo 3 years ago+ 1 comment

      what is 64 bit int ? Is it long long ?

      -1|
      ParentPermalink
      • ronak319 3 years ago+ 2 comments

        int64_t ; declare like this . This one is portable and can be used on every machine whether it is 64 or 32 because size of long int and long long int depend on machines also but int64_t guarantee on every machine. In C++;

        5|
        ParentPermalink
        • abhi15kk 3 years ago+ 1 comment

          Thanks a lot.. I used long long int. It gave me WA for 3 cases.. Declaring it your way helped me pass those cases.. I don't know why it is not accepting long long int.

          0|
          ParentPermalink
          • Saras_Arya 2 years ago+ 1 comment

            Was it test case 9, 10, 14. I am getting WA for only those.

            0|
            ParentPermalink
            • abhaykuma 11 months ago+ 0 comments

              resolved ?

              0|
              ParentPermalink
        • jimmyX 2 years ago+ 0 comments

          thanks man, i bought two test cases for that xD

          -1|
          ParentPermalink
    • amazinghacker 3 years ago+ 0 comments
      [deleted]
      -1|
      ParentPermalink
    • tubededentifrice 3 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • quick_dudley 3 years ago+ 0 comments

      That's weird: I was just using 32 bit ints and didn't have any problem.

      -4|
      ParentPermalink
    • kohei 3 years ago+ 0 comments

      You saved me!! Thank you!

      -2|
      ParentPermalink
    • sonicjoy2002 3 years ago+ 0 comments

      Damn! Should've read your comment before spending 5 hacko. Thank you.

      0|
      ParentPermalink
    • nitinyadav 3 years ago+ 0 comments

      Thank you

      0|
      ParentPermalink
    • HarryCho 3 years ago+ 0 comments

      Additional info : Overflow occurs on the answer. Value of N is in the range of int (fairly small).

      1|
      ParentPermalink
    • maverick55 3 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • royal146 3 years ago+ 0 comments

      Thanks

      -1|
      ParentPermalink
    • arunwizz 3 years ago+ 0 comments

      thanks .. 3 cases were failing with jave int, java long worked..

      -1|
      ParentPermalink
    • suprchan 3 years ago+ 0 comments

      Thank you :-). Failure to handle it costed 3 test cases!

      -1|
      ParentPermalink
    • Soumya_cbr 3 years ago+ 2 comments

      Hi, How to switch to 64 bit int in c??? Please help... i am also facing the overflow issue

      0|
      ParentPermalink
      • haha_ha 3 years ago+ 0 comments

        declare long long int datatype instead of declaring int

        0|
        ParentPermalink
      • juan_furattini 2 years ago+ 0 comments
        • C: long long int
        • C++: int64_t
        0|
        ParentPermalink
    • Dikaios 3 years ago+ 0 comments

      thanks

      -2|
      ParentPermalink
    • gopikaks 3 years ago+ 2 comments

      can u please tell me how to switch to 64-bit int

      0|
      ParentPermalink
      • gsnanda 3 years ago+ 0 comments

        For C++, use int64_t

        0|
        ParentPermalink
      • ShkKiit 2 years ago+ 0 comments

        long long instead of int in c++

        0|
        ParentPermalink
    • ShkKiit 2 years ago+ 0 comments

      Had to buy testcases for that :P Wish i saw your comment haha

      -1|
      ParentPermalink
    • guilin 2 years ago+ 3 comments

      the only thing I learn is that alwasy use Long the only thing I learn is that alwasy use Long the only thing I learn is that alwasy use Long --repeat 3 times if it's very oimportant,重要的事情说三遍

      6|
      ParentPermalink
      • skybrown6543 2 years ago+ 3 comments

        中国人出现了。。

        (盟友),+1s

        1|
        ParentPermalink
        • fengli97 2 years ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
        • rfeng2 2 years ago+ 2 comments

          盟友+1

          0|
          ParentPermalink
          • fasalirr 2 years ago+ 2 comments
            0|
            ParentPermalink
            • love_lion_1 2 years ago+ 0 comments
              [deleted]
              0|
              ParentPermalink
            • wensi 2 years ago+ 0 comments

              盟友+1

              0|
              ParentPermalink
          • love_lion_1 2 years ago+ 0 comments
            [deleted]
            0|
            ParentPermalink
        • love_lion_1 2 years ago+ 0 comments

          盟友+1

          0|
          ParentPermalink
      • zutianluo 1 year ago+ 0 comments

        喜相逢…

        0|
        ParentPermalink
      • h493263729 1 year ago+ 0 comments

        你好 哈哈

        0|
        ParentPermalink
    • bhanuchand 2 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • shengpu1126 2 years ago+ 0 comments

      Thank you very much for the tip! This is definitely something that programmers need to take care of: even though the algorithmic logic is right, be mindful of these details in practicality.

      0|
      ParentPermalink
    • AnamikaAna 2 years ago+ 0 comments

      I got all my test cases right after reading this comment :) Thanks a lot

      0|
      ParentPermalink
    • Chuyinzki 2 years ago+ 0 comments

      You are my hero.

      0|
      ParentPermalink
    • hi_kommineni 2 years ago+ 0 comments

      Thanks!!

      0|
      ParentPermalink
    • tomasz_polgrabia 2 years ago+ 0 comments

      I can only add my note: spending one hour on solving the only problem "integer overflow" (my algorithm was fine) without a possibility to look at the test cases makes my face ( ok, I will not embed any gifs, but you can imagine this) MAAAADDDDDDD. Task's author should warn at the beginning that the range of test cases' outputs exceed the normal range of the integer type.

      -1|
      ParentPermalink
    • abhinaw 2 years ago+ 0 comments

      Even 64-bit int is not working for two test cases. Though it helped me in one test case.

      First three test cases were not getting accepted. After using 64-bit int, two test cases are still not getting accepted.

      1|
      ParentPermalink
    • ajenal 2 years ago+ 0 comments

      Saved my day.

      0|
      ParentPermalink
    • parasgangwani292 2 years ago+ 0 comments

      thanks

      0|
      ParentPermalink
    • Mumbaikar007 2 years ago+ 0 comments

      You made my day !!

      0|
      ParentPermalink
    • kumar_malay888 2 years ago+ 1 comment

      this is my code and used java8 :- for coin change problem

      public static String CoinChange(int input1,int[] input2) { return CoinChange(input1,input2,0,new HashMap()); }

      public static String CoinChange(int input1,int[] input2,int a, HashMap<String,Long> memo)
      {
          int b = 1;
          int c = 0;
          long d = 0;
          String x = "";
          if(input1 == 0)
          {
              return (x = String.valueOf(b));
          }
          if(a >= input2.length)
          {
              return (x = String.valueOf(c));
          }
      
          String z = input1+"-"+a;
      
          if(memo.containsKey(z))
          {
             d = memo.get(z);
             return (x = String.valueOf(d));
          }
          int e = 0;
          long f = 0;
      
          while(e <= input1)
          {
              int g = input1 - e;
              f += CoinChange(input2, g, a+1,memo);
              e += input2[a];
          }
          memo.put(z,f);
          return(x = String.valueOf(f));
      
      
          and i was getting a error which is
          CandidateCode.java:43: error: incompatible types: int[] cannot be converted to int
              f += CoinChange(input2, g, a+1,memo);
      
      
              can anyone please solve this
      
      -1|
      ParentPermalink
      • RA1611003010504 10 months ago+ 0 comments

        f += CoinChange(input2, g, a+1,memo); You are missing an argument while passing the values here. Your first variable in the function definition is an int type and the second one is an array.

        0|
        ParentPermalink
    • AkankshaRajhans 1 year ago+ 1 comment

      This is my code in Java7 static long getWays(long n, long[] c){ // Complete this function long[] combinations=new long[(int)n]; combinations[0]=1; for(int j=0;j=c[j]) combinations[i]+=combinations[i-(int)c[j]]; } }

      return combinations[(int)n];
      

      } I am getting AArrayIndexOutOfBoundsException. Can anyone help ?

      -1|
      ParentPermalink
      • gk_2000 11 months ago+ 0 comments

        you can put code inside 3 backquotes in beginning and end to get formatting

        0|
        ParentPermalink
    • rwan7727 1 year ago+ 3 comments

      Passed all cases:

      int main() {
          int n;
          int m;
          cin >> n >> m;
          vector <long> c(m);
          for (int i=0;i<m;i++) cin >> c[i];
      
          vector <long> numways(n+1); // numways[x] means # ways to get sum x
          numways[0]=1; // init base case n=0
          
          // go thru coins 1-by-1 to build up numways[] dynamically
          // just need to consider cases where sum j>=c[i]    
          for (int i=0;i<m;i++) {
              for (int j=c[i];j<=n;j++) {
                  // find numways to get sum j given value c[i]
                  // it consists of those found earlier plus
                  // new ones.
                  // E.g. if c[]=1,2,3... and c[i]=3,j=5,
                  //      new ones will now include '3' with
                  //      numways[2] = 2, that is:
                  //      '3' with '2', '3' with '1'+'1'
                  numways[j]+=numways[j-c[i]]; 
              }
          }    
      
          cout << numways[n];    
          return 0;
      }
      
      27|
      ParentPermalink
      • chammika 1 year ago+ 0 comments

        This is the perfect answer ! Hats off!!

        1|
        ParentPermalink
      • jessica_0422 1 year ago+ 0 comments

        That makes sense, very clear! Thank you!

        0|
        ParentPermalink
      • bishty472 12 months ago+ 0 comments

        i dont understand what j is.

        2|
        ParentPermalink
    • mugu007 1 year ago+ 0 comments

      Thank You ... from 3 years in the Future.

      -5|
      ParentPermalink
    • mayank7577 5 months ago+ 0 comments

      why can not I use long long int instead of 64 bit int ?? using long long it is giving debugging output same as desired output but still it is showing wrong answer.

      0|
      ParentPermalink
  • lancerchao 3 years ago+ 3 comments

    A VERY helpful link for anyone who cannot understand the subproblems involved: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change

    55|
    Permalink
    • anonymouse_pal 3 years ago+ 0 comments

      Thanks! That really helped! :)

      0|
      ParentPermalink
    • ramdev64 3 years ago+ 0 comments

      Thanks. that was helpful :)

      0|
      ParentPermalink
    • Rav1T3ja 2 years ago+ 0 comments

      Good site for many Important Algorithms. Good contribution lancerchao

      1|
      ParentPermalink
  • mcervera 3 years ago+ 3 comments

    The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:

    (1) the number of ways you can make change for n using only the first m-1 coins.

    (2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).

    This data allows you to build the recurrence relation.

    40|
    Permalink
    • ricktetstall 2 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • suraj23patel 2 years ago+ 1 comment

      Can anyone please explain how is this recurresnce derived?

      0|
      ParentPermalink
      • mcervera 2 years ago+ 1 comment

        Posting the recurrence would be the same as posting the solution to the problem since it is the only thing that you need to do to solve it.

        Hint: define a bidimensional table. Each (m,n) position stores the number of ways you can obtain the amount "n" using only the first "m" coins. Define the boundary conditions and iteratively fill the table. The solution to the problem will be stored in position (M,N).

        3|
        ParentPermalink
        • zxnzysj 2 years ago+ 0 comments

          thanks for your hint

          0|
          ParentPermalink
    • YeahKey 2 years ago+ 0 comments

      Your hint really helped~ Thx

      0|
      ParentPermalink
  • Tsukuyomi1 2 years ago+ 9 comments

    Keeping it simple :D

    n, m = map(int,input().split())
    coins = list(map(int,input().split()))
    dp = [1]+[0]*n
    for i in range(m): 
        for j in range(coins[i], n+1): dp[j]+=dp[j-coins[i]]
    print(dp[-1])
    
    25|
    Permalink
    • multidynamic 2 years ago+ 0 comments

      👍

      0|
      ParentPermalink
    • sothisislife101 2 years ago+ 1 comment

      I've seen a lot of solutions similar to this one in other languages, but this is the first one I've seen in python. My solution is much more verbose, and I'm having difficulty understanding what exactly is going on here. Can someone walk me through it?

      0|
      ParentPermalink
      • Tsukuyomi1 2 years ago+ 0 comments

        dp[j] stores the number of solutions for j. For base case j=0, number of solutions is 1(not using any coin). Now in the for loop, i represents the number of coins you are using. Initially i=0, so you cannot create change for any j>0, hence dp[j]=0 for j>0. Now in each iteration you add a new coin and update the number of solutions for those j which have value not less than the value of ith coin. This update is just adding the number of solutions when we use the ith coin which is equal to the number of solutions of creating change for j-coins[i]. We are finally done when we use all the coins and so we print dp[n].

        13|
        ParentPermalink
    • diego_amicabile 2 years ago+ 2 comments

      Once you get around to understand it, this is a much better and straightforward solution IMHO. It is also more in line with the explanations given on Topcoder.

      I would sum up the algorithm this way.

      # Initialize an array of combination numbers for all money amounts from 0 until the target amount
      # For all coin values:
      #    for all money values starting from the coin value up to the target amount:
      #        get the number of combinations for the money value minus the coin value 
      #        add this to the number of combinations of the money value, because you can construct them just adding a coin to them 
      

      This is a more verbose version with descriptive variables, that allows you to see the algorithm in action:

      import sys
      target_money, coin_count = input().strip().split(' ')
      target_money, coin_count = [int(target_money), int(coin_count)]
      coins = list(map(int, input().strip().split(' ')))
      combinations = [1] + [0] * target_money
      
      for coin_index in range(coin_count):
          print("Combinations before processing coin {}: {}".format(coins[coin_index], combinations), file=sys.stderr)
          for money in range(coins[coin_index], target_money + 1):
              if (combinations[money - coins[coin_index]]) > 0:
                  print("    Combinations for {} added to combinations for {} : {} += {}".format(money - coins[coin_index], money, combinations[money], combinations[money - coins[coin_index]]), file=sys.stderr)
                  combinations[money] += combinations[money - coins[coin_index]]
          print("Combinations after processing coin {}: {}".format(coins[coin_index], combinations), file=sys.stderr)
      
      print("Combinations for {} : {}".format(target_money, combinations[target_money]), file=sys.stderr)
      print(combinations[target_money])
      

      Now for instance, for test case

      10 4
      2 5 3 6
      

      it will show the process on stderr:

      Combinations before processing coin 2: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
          Combinations for 0 added to combinations for 2 : 0 += 1
          Combinations for 2 added to combinations for 4 : 0 += 1
          Combinations for 4 added to combinations for 6 : 0 += 1
          Combinations for 6 added to combinations for 8 : 0 += 1
          Combinations for 8 added to combinations for 10 : 0 += 1
      Combinations after processing coin 2: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
      Combinations before processing coin 5: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
          Combinations for 0 added to combinations for 5 : 0 += 1
          Combinations for 2 added to combinations for 7 : 0 += 1
          Combinations for 4 added to combinations for 9 : 0 += 1
          Combinations for 5 added to combinations for 10 : 1 += 1
      Combinations after processing coin 5: [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2]
      Combinations before processing coin 3: [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2]
          Combinations for 0 added to combinations for 3 : 0 += 1
          Combinations for 2 added to combinations for 5 : 1 += 1
          Combinations for 3 added to combinations for 6 : 1 += 1
          Combinations for 4 added to combinations for 7 : 1 += 1
          Combinations for 5 added to combinations for 8 : 1 += 2
          Combinations for 6 added to combinations for 9 : 1 += 2
          Combinations for 7 added to combinations for 10 : 2 += 2
      Combinations after processing coin 3: [1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4]
      Combinations before processing coin 6: [1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4]
          Combinations for 0 added to combinations for 6 : 2 += 1
          Combinations for 2 added to combinations for 8 : 3 += 1
          Combinations for 3 added to combinations for 9 : 3 += 1
          Combinations for 4 added to combinations for 10 : 4 += 1
      Combinations after processing coin 6: [1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5]
      Combinations for 10 : 5
      
      10|
      ParentPermalink
      • tigerleapgorge 1 year ago+ 0 comments

        This is great. Thank you explaining!

        0|
        ParentPermalink
      • shankarpenore 8 months ago+ 0 comments

        can you please explain the code of processing coin and after prossing :

        Combinations for 0 added to combinations for 5 : 0 += 1 Combinations for 2 added to combinations for 7 : 0 += 1 Combinations for 4 added to combinations for 9 : 0 += 1 Combinations for 5 added to combinations for 10 : 1 += 1

            can you plz explain these combitions
        
        0|
        ParentPermalink
    • krozaine 1 year ago+ 0 comments

      You are simply awesome!! Made my day :)

      0|
      ParentPermalink
    • Yu_Zhao1 1 year ago+ 1 comment

      How could any human beeing possibly come to this solution on his own?

      4|
      ParentPermalink
      • metamemelord 1 year ago+ 0 comments

        It's all practice dude. THis question in specific, is pretty straight forward.

        -1|
        ParentPermalink
    • nitishks007 11 months ago+ 0 comments

      Nice! if we change the order of loop ( i inside j) we will get all possible ways of getting the change. Basically 2,2,5 will counted differently from 2,5,2

      0|
      ParentPermalink
    • wangjiehui11235 10 months ago+ 0 comments

      Thank you~

      0|
      ParentPermalink
    • shubham10dulkar1 7 months ago+ 1 comment

      def getWays(n, c):

      l=len(c)
      ways=[[0 for p in range(n+1) ] for m in range(l)]
      
      for p in range(0,l):
          ways[p][0]=1
      
      for p in range(0,n+1,c[0]):
          #print(p)
          ways[0][p] = 1
      
      for i in range(1,l):
          for j in range(1,n+1):
              p=j-c[i]
              if p <0:
                  x=0
              else:    
                  x=ways[i][p]
              y=ways[i-1][j]
              ways[i][j]= x+y
      print(long(ways[l-1][n]))
      

      i m getting expected output still test case not passing

      for example

      input:

      10 4

      2 5 3 6

      expected output: 5

      debug output : 5

      still test case fails

      plzz help

      0|
      ParentPermalink
      • fqzhou2012 6 months ago+ 0 comments

        your code is right. However, the website generated codes make you have to add a standard output codes ,like fptr.write(str(ways)) ,before fptr.close(). Besides, your function has to return the output value (ways[l-1][n] rather than printing it (This way the system will regard it as debug)

        0|
        ParentPermalink
    • b_hus_han 2 months ago+ 0 comments

      amazing way to reduce space complexity as well brilliant

      0|
      ParentPermalink
  • kittenintofu 3 years ago+ 3 comments

    For someone new to coding, this is a very interesting question and I def learned quite a lot from it. I'm writing this post just to help myself remember it.

    The core concept is:

    calculator(coins, numToUse, sum) = calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]); basically saying for the current sum, it can and only can be achieved by two sub-cases:

    (1). you use one less kind of coins, and still achevie this sum.

    (2). you still use the same set of coins, but achieve (sum-oneCoinValue). This "oneCoinValue" is the value of the coin that you eliminates in the sub-case (1) And if you total these two cases up, you get what you want.

    And the next step is to speed up your program. If you think about it, there are some potential redundent calculations-- for a lot of sub-cases, they ended up trying to calculate the same sum. And here, I made my first improvement, and it FAILED hardcore... i used an array of size sum, as a look up table. Have I calculated the current sum already, if so, don't do the recursive call, but return the value that was already saved in the table; if not do the recursive call, and save the final return value to the lookup table.

    Apparently, that approach did NOT end up well. I couldn't even get the first two mini test cases passed. And then I realized, apparently, there are two important arguments that are passed in: sum AND the numToUse, which basically tells you how many types of coins that you are allowed to use to get the sum. So if you only use a one dimentioanl array to save the result, that's not enough. Using coins {1,2,3} to achieve the number 10 of course is not going to be the same as if you only allowed to use coins {1,2}. The lookup table needs to be 2D. And the major calculator function look like this:

    private static long calculator(int[] coins, int numToUse, int sum){
    
        if( sum ==0 ){
            return 1;
        }
    
        else if(sum < 0 ){
            return 0;
        }
        else if (numToUse <= 0){
            return 0;
        }
        else {
            if (done[sum][numToUse] == -7){
               done[sum][numToUse] =  calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]) ;
            }
           return done[sum][numToUse];
        }
    }
    
    
    // -7 is just the value that I intialize the array done, I picked it becuase I like number 7, haha
    
    18|
    Permalink
    • svadali2 3 years ago+ 0 comments

      thank you for that, even though you wrote it for yourself :)

      0|
      ParentPermalink
    • stanfordkansas 3 years ago+ 1 comment

      With yr impelemetation:

      -Time Complexity is O(2^m) because of all possible subsets of the given coins

      -Space Complexity is O(nm)

      Is it right?

      0|
      ParentPermalink
      • aitrop 3 years ago+ 1 comment

        Seems like an overly complicated recursive solution to me. Surprised if it passed runtime tests.

        -3|
        ParentPermalink
        • pendell 2 years ago+ 0 comments

          Others have downvoted the comment, and the reason why is that it is essentally the same solution as in the editorial. There are some additional test cases that the editorial doesn't have, but the logic is otherwise sound.

          The reason it passes the runtime tests is because of the if (done[sum][numToUse] == -7) check. This ensures that we only compute solutions one time -- if we need the same solution again, we just use the previously computed solution.

          1|
          ParentPermalink
    • ammar_lokh1234 1 year ago+ 1 comment

      Hey I have a javascript program done the same way as OP, however I'm getting a runtime time error with my "done" array. I'm new to JS so can somebody help me spot the issue?

      function getWays(n, c, m, done){
          // Complete this functionc
          var res=0;
          if(n==0) {  
              return 1;
          }
          if(n<0)
              return 0;
          if(m<=0)
              return 0;
          else {
              // Here is where I get the error: TypeError: Cannot read property '2' of undefined
                 if(done[n][m]==-1) 
                      done[n][m] = getWays(n-c[m-1],c,m, done) + getWays(n,c,m-1, done);  
                  return done[n][m];
          }
      }
      
      function main() {
          var n_temp = readLine().split(' ');
          var n = parseInt(n_temp[0]);
          var m = parseInt(n_temp[1]);
          var done = [];
          c = readLine().split(' ');
          c = c.map(Number);
          for(var i=0;i<n;i++){
              var col = [];
              for(var j=0;j<m;j++) {
                  col[j] =-1;
              }
              done[i] = col;
          }
          // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
          var ways = getWays(n, c, m-1, done);
          console.log(ways);
      }
      
      1|
      ParentPermalink
      • schrecka 2 months ago+ 0 comments

        I have the same problem did you figure this out

        0|
        ParentPermalink
  • ishtiaque_h 2 years ago+ 1 comment

    There's a very good explanation from Gayle (author of Cracking the Coding Interview book) for this problem in YouTube. Watch: https://www.youtube.com/watch?v=sn0DWI-JdNA

    12|
    Permalink
    • gravitation 12 months ago+ 0 comments

      Thanks

      Nothing in this thread really helped me at all, but after watching one minute of this video I realized the error in my approach to the problem

      0|
      ParentPermalink
  • nelson_a_antunes 2 years ago+ 3 comments

    DP in python2 with 1D list/array:

    value,_ =  map(int,raw_input().strip().split(' '))
    coins = map(int,raw_input().strip().split(' '))
    
    ways = [0]*(value+1)
    
    for coin in coins:
        if coin > value: #if coin > value, there's no reason to use it
            continue 
        ways[coin]+=1 #coin by itself as a set
        
        for i in range(coin+1,value+1): #fill the remaining sets with a new possibility with this coin 
            ways[i] += ways[i-coin]
    
    print ways[value]
    
    11|
    Permalink
    • rswaghmare 2 years ago+ 0 comments

      Wow! Did you develop this algorithm yourself?

      1|
      ParentPermalink
    • katsmanva 4 months ago+ 0 comments

      I was thinking about implementation for 2 todays, man, brilliant solution!

      0|
      ParentPermalink
    • isharth 2 months ago+ 0 comments

      genius

      0|
      ParentPermalink
  • pujakuntal123 9 months ago+ 3 comments

    Ridiculous .. all answer come correct but compiler throwing message ..wrong answer

    9|
    Permalink
    • logesssh 8 months ago+ 2 comments

      add this line to main class

      bufferedWriter.write(String.valueOf(ways)); bufferedWriter.newLine();

      2|
      ParentPermalink
      • vverma14 8 months ago+ 1 comment

        what to do in case of c++; also getting wrong answer .

        4|
        ParentPermalink
        • feroce 4 months ago+ 0 comments

          You can add the following to main before the close statement:

          fout << ways;

          Not sure why it is broken...

          1|
          ParentPermalink
      • JaySingh566 7 months ago+ 0 comments

        Thanks man!

        0|
        ParentPermalink
    • anil09 6 months ago+ 0 comments

      In C, i faced the same problem. You should print the message in file. I used fprintf instead of printf. And the problem got resolved.

      0|
      ParentPermalink
    • dnavalta 6 months ago+ 0 comments

      I think the solution by logesssh is in java, but I don't know for sure. In python, the answer is to have your function return the value, then after the function call in main use

      fptr.write(str(ways))
      
      0|
      ParentPermalink
  • akshaykabra 4 years ago+ 3 comments

    the input format of the question is not clear/really_bad. Also no constraints are given.

    9|
    Permalink
    • PRASHANTB1984 4 years ago+ 2 comments

      That section got wiped out along with some other changes. We'll be restoring it in a while.

      0|
      ParentPermalink
      • roshan_santhosh 4 years ago+ 1 comment

        Its been 9 days already. When will t be changed? The format is very unclear.

        2|
        ParentPermalink
        • PRASHANTB1984 4 years ago+ 2 comments

          just updated it. Can you refresh?

          0|
          ParentPermalink
          • akshaykabra 4 years ago+ 0 comments

            Sir if number of coins to be taken would have been in input format it would be easier to take input.. can you please update the format??

            0|
            ParentPermalink
          • JaskaranSingh 4 years ago+ 1 comment

            What is the bound on M-the number of coins?

            The input format isn't good.Right now the problem looks more of a challenge of input parsing rather than DP.

            3|
            ParentPermalink
            • akshaykabra 4 years ago+ 0 comments

              :D :D :D agree !! :)

              0|
              ParentPermalink
      • amazinghacker 3 years ago+ 1 comment
        [deleted]
        0|
        ParentPermalink
        • quick_dudley 3 years ago+ 0 comments

          No, it's not necessary: I just used 2 loops.

          0|
          ParentPermalink
    • amazinghacker 3 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • bossgates 3 years ago+ 0 comments
      • Use long instead of int
      • In some cases, Ci > N
      -1|
      ParentPermalink
  • CamJohnson26 7 months ago+ 0 comments

    The Python 3 template is broken. After the call to getWays should be this line: fptr.write(str(ways))

    5|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature