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

Source: codewars | Difficulty: EASY
Tags: Mathematics

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


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)