This notebook was prepared by [mrb00l34n](http://github.com/mrb00l34n). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Challenge Notebook

Problem: Counting Ways of Making Change

Explanation
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

Explanation

How many ways are there of making change for n, given an array of distinct coins? For example:

Input: n = 4, coins = [1, 2]

Output: 3. 1+1+1+1, 1+2+1, 2+2, would be the ways of making change.

Note that a coin can be used any number of times, and we are counting unique combinations.

Test Cases

Input: n = 0, coins = [1, 2] -> Output: 0
Input: n = 100, coins = [1, 2, 3] -> Output: 884
Input: n = 1000, coins = [1, 2, 3...99, 100] -> Output: 15658181104580771094597751280645

Algorithm

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

Code



In [ ]:

    
def change_ways(n, coins):
    # TODO: Implement me
    return n

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [ ]:

    
# %load test_coin_change_ways.py
from nose.tools import assert_equal


class Challenge(object):

    def test_coin_change_ways(self,solution):
        assert_equal(solution(0, [1, 2]), 0)
        assert_equal(solution(100, [1, 2, 3]), 884)
        assert_equal(solution(1000, range(1, 101)), 
                     15658181104580771094597751280645)
        print('Success: test_coin_change_ways')


def main():
    test = Challenge()
    test.test_coin_change_ways(change_ways)


if __name__ == '__main__':
    main()

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.