# 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[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:

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

## 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 different domain including SAP, Blockchain, AI and Web Development.