# Making Change

Complete the method that will determine the minimum number of coins needed to make change for a given amount in American currency.

Coins used will be half-dollars, quarters, dimes, nickels, and pennies, worth 50¢, 25¢, 10¢, 5¢ and 1¢, respectively. They'll be represented by the symbols `H`, `Q`, `D`, `N` and `P` (symbols in Ruby, strings in in other languages)

The argument passed in will be an integer representing the value in cents. The return value should be a hash/dictionary/object with the symbols as keys, and the numbers of coins as values. Coins that are not used should not be included in the hash. If the argument passed in is 0, then the method should return an empty hash.

## Examples

```python
make_change(0)   #-->  {}
make_change(1)   #-->  {"P":1}
make_change(43)  #-->  {"Q":1, "D":1, "N":1, "P":3}
make_change(91)  #-->  {"H":1, "Q":1, "D":1, "N":1, "P":1}
```

#### **If you liked this kata, check out [Part 2](https://www.codewars.com/kata/making-change-part-2/ruby).**

Difficulty: introductory

Starter code:

def make_change(amount):
	

Solutions:
BASE = {"H": 50, "Q": 25, "D": 10, "N": 5, "P": 1}

def make_change(n):
    r = {}
    for x, y in BASE.items():
        if n >= y:
            r[x], n = divmod(n, y)
    return r

def make_change(amount):
    H = 50
    Q = 25
    D = 10
    N = 5
    P = 1
    change = {}
    while amount > 0:    
        if (amount - H) >= 0:
            change["H"] = 1
            amount -= H
            while amount >= H:
                change["H"] += 1
                amount -= H
        elif (amount - Q) >= 0:
            change["Q"] = 1
            amount -= Q
            while amount >= Q:
                change["Q"] += 1
                amount -= Q
        elif (amount - D) >= 0:
            change["D"] = 1
            amount -= D
            while amount >= D:
                change["D"] += 1
                amount -= D
        elif (amount - N) >= 0:
            change["N"] = 1
            amount -= N
            while amount >= N:
                change["N"] += 1
                amount -= N
        elif (amount - P) >= 0:
            change["P"] = 1
            amount -= P
            while amount >= P:
                change["P"] += 1
                amount -= P                
        else:       
            return change
    return change            

COINS = dict(H=50, Q=25, D=10, N=5, P=1)


def make_change(amount):
    result = {}
    for coin, value in COINS.items():
        if amount >= value:
            result[coin], amount = divmod(amount, value)
    return result

def make_change(amount):
    coins = {'H':50,'Q':25,'D':10,'N':5,'P':1}
    change = {}
    for coin in coins:
        if amount >= coins[coin]:
            change[coin], amount = divmod(amount, coins[coin])
    return change

from collections import defaultdict

coins = (
    ("H", 50),
    ("Q", 25),
    ("D", 10),
    ("N", 5),
    ("P", 1),
)

def make_change(amount):
    result = defaultdict(int)
    for coin, value in coins:
        while amount >= value:
            result[coin] += 1
            amount -= value
    return result


def make_change(amount):
    coins = {
        'H' : 50,
        'Q' : 25,
        'D' : 10,
        'N' : 5,
        'P' : 1
    }
    
    dict = {}
    
    for key in coins:
        if amount >= coins[key]:
            dict[key], amount = divmod(amount, coins[key])
            
    return dict

def make_change(amount):
    H = 50
    Q = 25
    D = 10
    N = 5
    P = 1
    change = {}
    while amount > 0:    
        if (amount - H) >= 0:
            change["H"] = 1
            amount -= H
            while amount >= H:
                change["H"] += 1
                amount -= H
                if amount < H:
                    continue
        elif (amount - Q) >= 0:
            change["Q"] = 1
            amount -= Q
            while amount >= Q:
                change["Q"] += 1
                amount -= Q
                if amount < Q:
                    continue
        elif (amount - D) >= 0:
            change["D"] = 1
            amount -= D
            while amount >= D:
                change["D"] += 1
                amount -= D
                if amount < Q:
                    continue
        elif (amount - N) >= 0:
            change["N"] = 1
            amount -= N
            while amount >= N:
                change["N"] += 1
                amount -= N
                if amount < N :
                    continue
        elif (amount - P) >= 0:
            change["P"] = 1
            amount -= P
            while amount >= P:
                change["P"] += 1
                amount -= P
                if amount < P:
                    return change                
        else:       
            return change
    return change            

coins = (('H', 50), ('Q', 25), ('D', 10), ('N', 5), ('P', 1))

def make_change(amount):
    result = {}
    for x,y in coins:
        q, amount = divmod(amount, y)
        if q: result[x] = q
        if not amount: return result

def make_change(amount):
    result = {}
    if amount == 0:
        return result
    else:
        halves = amount // 50
        remainder = amount % 50
        quarters = remainder // 25
        remainder = remainder % 25
        dimes = remainder // 10
        remainder = remainder % 10
        nickels = remainder // 5
        pennies = remainder % 5
        if halves > 0:
            result['H'] = halves
        if quarters > 0:
            result['Q'] = quarters
        if dimes > 0:
            result['D'] = dimes
        if nickels > 0:
            result['N'] = nickels
        if pennies > 0:
            result['P'] = pennies
    return result

d = [("H",50),("Q",25),("D",10),("N",5),("P",1)]
make_change=lambda m,i=0,cng=[]:make_change(*([m%d[i][1],i+1,cng+[(d[i][0],m//d[i][1])]] if m>=d[i][1] else [m,i+1,cng])) if m else dict(cng)

'''cng = {}
for i,j in d.items():
        if money>=j:
            cng[i] = money//j
            money %= j
return cng'''