Thank you

Thank you !

thanks

THANKS! :D

Did it in python 8-)

thanks :P

Another thanks.

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

what is 64 bit int ? Is it long long ?

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

You saved me!! Thank you!

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

Thank you

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

Thanks

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

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

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

thanks

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

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

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,重要的事情说三遍

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.

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

You are my hero.

Thanks!!

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.

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.

Saved my day.

thanks

You made my day !!

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

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 ?

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;
}

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

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.

Thanks! That really helped! :)

Thanks. that was helpful :)

Good site for many Important Algorithms. Good contribution lancerchao

Can anyone please explain how is this recurresnce derived?

Your hint really helped~ Thx

👍

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?

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

You are simply awesome!! Made my day :)

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

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

Thank you~

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

amazing way to reduce space complexity as well brilliant

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

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?

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);
}

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

Wow! Did you develop this algorithm yourself?

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

genius

add this line to main class

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

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.

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))

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

• Use long instead of int
• In some cases, Ci > N