Python program for coin change using Python

Introduction

The task is to find the number of ways we can make the change of given N cents having infinite supply of Coins = { C1, C2,C3 …. Cn}  valued coins.

Python program for coin change using Python

Program

Approach 1

def sol(array, length, Ncents):




    result_table = [[0 for count in range(length)] for count in range(Ncents+1)]




    for x in range(length):

        result_table[0][x] = 1




# Fill table in bottom up manner

    for x in range(1, Ncents+1):

        for y in range(length):

#Do not contain lth coin

            count = result_table[x - array[y]][y] if x-array[y] >= 0 else 0

#Contain lth coin

            count1 = result_table[x][y-1] if y >= 1 else 0




            result_table[x][y] = count + count1




    return result_table[Ncents][length-1]




ip_array = [1, 2, 5, 10]

Ncents = int(input("Enter the value: "))

print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))

Output:

Python program for coin change using Python Output 1

Approach 2

def sol(arr,length, N):




    result_table = [0 for k in range(N+1)]




    result_table[0] = 1

# Update table if index >= value of picked coin

    for x in range(0,length):

        for y in range(arr[x],N+1):

            result_table[y] += result_table[y-arr[x]]




    return result_table[N]




ip_array = [1, 2, 5, 10]

Ncents = int(input("Enter the value: "))

print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))

Output

Python program for coin change using Python Output 2

Explanation

There can be two sub-problems to the given problem:

  • Solution containing nth coin
  • Solution do not contacting nth coin.

The total count can be obtained by adding both the solutions.

Author

  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.

    View all posts

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.