A country has coins with denominations
```python
coins_list = d1 < d2 < · · · < dn.
```
You want to make change for n cents, using the smallest number of coins.

```python
# Example 1: U.S. coins
d1 = 1 d2 = 5 d3 = 10 d4 = 25

## Optimal change for 37 cents – 1 quarter, 1 dime, 2 pennies.

# Example 2: Alien Planet Z coins
Z_coin_a = 1 Z_coin_b = 3 Z_coin_c = 4

## Optimal change for 6 cents - 2 Z_coin_b's
```

Write a function that will take a list of coin denominations and a desired amount and provide the least amount of coins needed.

Difficulty: introductory

Starter code:

def loose_change(coins_list, amount_of_change):
	

Solutions:
from collections import deque

def loose_change(coins_list, amount_of_change):
    q = deque([(0, amount_of_change)])

    while q:
        l, a = q.popleft()
        if a == 0:
            return l
        q.extend((l + 1, a - i) for i in coins_list if a >= i)

def loose_change(coins_list, amount):
    solution = [0] + [amount + 1] * amount
    for atmc in range(1, amount + 1):
        for coin in coins_list:
            if coin <= atmc:
                solution[atmc] = min(solution[atmc], solution[atmc - coin] + 1)
    return -1 if solution[amount] > amount else solution[amount]

def loose_change(coins_list, amount_of_change):   
    n, i, t = 0, 0, amount_of_change
    coins_list.sort(reverse = True)
    while amount_of_change >= 0 and i < len(coins_list): 
        if amount_of_change - coins_list[i] >= 0: 
            n += 1
            amount_of_change -= coins_list[i]
        else: i += 1
    return min([int(t/i) for i in coins_list if t % i == 0] + [n])
    
'''
second version
def loose_change(coins_list, amount_of_change):   
    coins, i, t = 0, 0, amount_of_change
    coins_list.sort(reverse = True)
    while amount_of_change > 0:
        tem = divmod(amount_of_change, coins_list[i])
        coins += tem[0]
        amount_of_change -= tem[0]*coins_list[i]
        i += 1
    aa = [int(t/i) for i in coins_list if t % i == 0] + [coins]
    return min(aa)
'''

def loose_change(coins_list, amount_of_change):
    if len(coins_list) == 1: return amount_of_change
    return min(
        loose_change(coins_list[:-1], amount_of_change),
        amount_of_change // coins_list[-1] + loose_change(coins_list[:-1], amount_of_change % coins_list[-1])
    )

def loose_change(c, a):
    l, n = 0, 0
    s = sorted([a//i for i in c if i > 1 and a % i == 0])
    for i in range(len(c)-1, -1, -1):
        k = (a - l)//c[i]
        n += k
        if l + k * c[i] <= a:
            l += k * c[i]
    return min(n, s[0]) if s else n


def loose_change(coins, change):
  return search(sorted(coins, reverse=True), change)

def search(coins, x, n=0):
  if x == 0: return n
  m = 9999
  for c in coins:
    if x >= c:
      q, r = divmod(x, c)
      m = min(m, search(coins, r, n + q))
  return m

def loose_change(coins_list, amount_of_change):
    coins_amount = [0] + [float('inf')] * amount_of_change
    for i in range(1, amount_of_change + 1):
        coins_amount[i] = min(coins_amount[i - c] for c in coins_list if c <= i) + 1
    return coins_amount[-1]

from itertools import combinations_with_replacement as combos

def loose_change(coins_list, amount_of_change):
    least_list = []
    for x in range(len(coins_list)):
        for combo in combos(coins_list, x + 1):
            if sum(combo) == amount_of_change:
                least_list.append(len(combo))
    return min(least_list)

def loose_change(coins_list, amount_of_change):
    changes = [1 if n+1 in coins_list else amount_of_change*2 for n in range(amount_of_change)]
    for i in range(amount_of_change):
        for c in coins_list:
            if i+c<amount_of_change: changes[i+c] = min(changes[i+c],changes[i]+1)
    return changes[amount_of_change-1]

def loose_change(coins_list, amount_of_change):
    if amount_of_change == 0:
        return 0
    elif amount_of_change < 0 or len(coins_list) == 0:
        return float('inf')
    else:
        with_first_coin = loose_change(coins_list, amount_of_change - coins_list[-1])
        without_first_coin = loose_change(coins_list[:-1], amount_of_change)
        return min(with_first_coin + 1, without_first_coin)