Select Page

# Python program for coin change using Python

by | Jul 19, 2021 | Python Programs

Home » Python » Python Programs » 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. ## 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[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: ### Approach 2

```def sol(arr,length, N):

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

result_table = 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 ## 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

• A Full Stack Developer with 10+ years of experience in technical content creation.

• 