# 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.

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