Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Coin change - the number of ways

    Given a money system that consists of n coins, each coin has a positive value . You are asked to find the number of ways to obtain a total amount of x by using the coins.
    For instance, if the coin values are and we need to obtain 5, there are 4 different ways to do that: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, and 1 + 1 + 1 + 1 + 1. Unlike the combination sum, here the order doesn’t matter - we’re only interested in the multiset of coins that we use.

    Input

    The first line of the input contains two integers n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).
    The next line contains n space-separated integers (1 ≤ ).

    Output

    The program should print the number of ways possible to obtain x using the given coins. As the answer can get very large, you are asked to print it modulo .

    Examples

    Input
    Output
    3 5 1 2 5
    4
    3 9 2 3 5
    3

    Explanation

    1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, and 1 + 1 + 1 + 1 + 1
    1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
     

    Tutorial

    Notice that if we store a state with d[s] where d[s] is the number of different ways to obtain the sum s by using the coins, we will have an issue of double counting where we would count the same set of coins several times. So, for the set of 1 + 2 + 2 (which should be counted only once), we would have it counted 3 times for all their combinations: 1 + 2 + 2, 2 + 1 + 2, and 2 + 2 + 1.
    To address this issue, we would count the number of ways to obtain the value s by processing all the coins up to ci (ci is the index of the coin in the array c). We are allowed to not use ci at all or use it multiple times - all of that is captured in the state. So, our state d[s][ci] would represent the number of ways to obtain the sum s by processing all the coins up to ci.
     
    There are 2 transitions that can get us from some of the previous states to the current d[s][ci] (the index of the current coin is ci and its value is val):
    1. We could not use the coin ci at all → d[s][ci - 1]
    1. We could use the coin ci for 0, 1, 2, … k times → d[s - val][ci]
    So, the total number of ways to obtain the sum s with all the coins up to ci would be the sum of all the transitions from the previous states described above.
     
    c = [...]
    x = ...
    # Initialize d with x+1 rows and len(c) columns of 0s
    d = [[0] * len(c) for _ in range(x + 1)]
    We can start by processing the first coin and update the state d[s][0] for all possible sums of s using the first coin. Then move on to the second coin and update all the states d[s][1]. Then to the third one - update d[s][2] and so on up until reaching the last coin.
    After processing all the coins, we can print the number of possible ways to reach the sum x by printing the state of reaching x after processing the last coin - d[x][len(c) - 1]:
    for ci, val in enumerate(c):      # Iterate over coins one-by-one
        d[0][ci] = 1                  # Possible to obtain sum of 0 with no coins
        for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
            if ci - 1 >= 0:           # (1) Not use ci at all
                d[s][ci] += d[s][ci - 1]
            if s - val >= 0:          # (2) Use ci for 0+ times
                d[s][ci] += d[s - val][ci]
    
    print(d[x][len(c) - 1])
     
    😎 Can you think of a way to keep a one-dimensional list for d?
    We process the coins one by one, so, it’s possible to throw away all the computed states for the coin ci - 2 and before. On each iteration, we’re only interested in the current coin ci and the previous coin ci - 1. So, we can keep the previous coin’s state in one array and the current coin’s state in another.
    😎 Can you think of a way to not use any auxiliary array and only use a 1-dimensional d?
    We can notice that the only operation from the previous coin’s state is the addition of prev[s] to d[s]. So, we can omit keeping the previous array at all:
    # Initialize d x+1 items
    d = [1] + [0] * x                 # Possible to obtain sum of 0 with no coins
    
    for ci, val in enumerate(c):      # Iterate over coins one-by-one
        for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
            if s - val >= 0:          # (2) Use ci for 0+ times
                d[s] += d[s - val]
            d[s] %= MOD
    
    print(d[x])
     

    Constraints

    Time limit: 2 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue