Given an infinite supply of each denomination of Indian currency { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } and a target value N.
Find the minimum number of coins and/or notes needed to make the change for Rs N. You must return the list containing the value of coins required. 
Example 1:
Input: N = 43
Output: 20 20 2 1
Explaination: 
Minimum number of coins and notes needed 
to make 43. 
Example 2:
Input: N = 1000
Output: 500 500
Explaination: minimum possible notes
is 2 notes of 500.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minPartition() which takes the value N as input parameter and returns a list of integers in decreasing order.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def minPartition(self, N):

        # code here

Solutions:
class Solution:

	def minPartition(self, n):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		l = []
		i = len(coins) - 1
		while n != 0 and i >= 0:
			if coins[i] > n:
				i -= 1
			else:
				n -= coins[i]
				l.append(coins[i])
		return l


class Solution:

	def minPartition(self, N):
		currency = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		i = len(currency) - 1
		res = []
		while i >= 0 and N != 0:
			if N >= currency[i]:
				quotient = N // currency[i]
				res += [currency[i]] * quotient
				N -= currency[i] * quotient
			i -= 1
		return res


class Solution:

	def minPartition(self, N):
		arr = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		count = []
		while N != 0:
			for coin in arr:
				if coin <= N:
					n = N // coin
					N = N - N // coin * coin
					for i in range(n):
						count.append(coin)
		return count


class Solution:

	def minPartition(self, N):
		set_list = [None] * N
		coins = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}

		def find_min_set(coins, set_list, n):
			min_set = []
			min_set_len = float('Inf')
			for coin in coins:
				if coin == n:
					cur_set = [coin]
					cur_set_len = 1
				elif coin < n:
					diff = n - coin
					cur_set = set_list[diff - 1] + [coin]
					cur_set_len = len(set_list[diff - 1]) + 1
				else:
					continue
				if cur_set_len < min_set_len:
					min_set_len = cur_set_len
					min_set = cur_set
			min_set.sort(reverse=True)
			set_list[n - 1] = min_set
		for i in range(N):
			find_min_set(coins, set_list, i + 1)
		return set_list[N - 1]


class Solution:

	def minPartition(self, N):
		money = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		result = []
		for i in range(9, -1, -1):
			result += [money[i]] * (N // money[i])
			N = N % money[i]
			if N == 0:
				break
		return result


class Solution:

	def minPartition(self, N):
		l = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		i = 0
		a = []
		while i < len(l):
			if l[i] > N:
				i += 1
			else:
				a.append(l[i])
				N -= l[i]
		return a


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		res = []
		for i in range(len(coins) - 1, -1, -1):
			while N >= coins[i]:
				N -= coins[i]
				res.append(coins[i])
		return res


class Solution:

	def minPartition(self, sm):
		(arr, out) = ([1, 2, 5, 10, 20, 50, 100, 200, 500, 2000][::-1], [])
		for i in arr:
			if sm // i > 0:
				out.extend([i] * (sm // i))
				sm -= i * (sm // i)
		return out


class Solution:

	def minPartition(self, amount):
		denominations = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		n = len(denominations)
		i = n - 1
		ans = []
		while i >= 0:
			if amount < denominations[i]:
				i -= 1
			elif amount == denominations[i]:
				ans.append(denominations[i])
				break
			else:
				ans.append(denominations[i])
				amount -= denominations[i]
		return ans


class Solution:

	def minPartition(self, N):
		p = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		ans = []
		for i in range(N):
			for i in p:
				if N >= i:
					ans.append(i)
					N = N - i
					break
			if N == 0:
				break
		return ans


class Solution:

	def minPartition(self, N):
		u = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		u = u[::-1]
		i = 0
		v = []
		while N != 0:
			if N >= u[i]:
				N = N - u[i]
				v.append(u[i])
			else:
				i += 1
		return v


class Solution:

	def minPartition(self, N):
		x = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		list = []
		while N != 0:
			for e in range(10):
				if x[e] <= N:
					N = N - x[e]
					list.append(x[e])
					break
		return list


class Solution:

	def minPartition(self, N):
		coins = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		ans = []
		i = 0
		while i < len(coins) or N <= 0:
			while i < len(coins) and coins[i] > N:
				i += 1
			if i >= len(coins):
				break
			N -= coins[i]
			ans.append(coins[i])
		return ans


class Solution:

	def minPartition(self, N):
		coinsList = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		coinsList = coinsList[::-1]
		coins = []
		while N > 0:
			for coin in coinsList:
				if N >= coin:
					coins.append(coin)
					N -= coin
					break
		return coins


import math

class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		coins.sort(reverse=True)
		ans = []
		for coin in coins:
			if coin > N or N <= 0:
				continue
			div = math.floor(N / coin)
			for i in range(div):
				ans.append(coin)
			N -= coin * div
		return ans


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		while N > 0:
			for i in range(9, -1, -1):
				num = N // coins[i]
				ans += [coins[i]] * num
				N = N % coins[i]
		return ans


class Solution:

	def minPartition(self, N):
		ans = []
		arr = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		for x in arr:
			coin = N // x
			ans += [x] * coin
			N = N % x
		return ans


import bisect

class Solution:

	def minPartition(self, N):
		arr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		i = 9
		while i >= 0:
			if N >= arr[i]:
				ans.append(arr[i])
				N -= arr[i]
			else:
				i -= 1
			if N <= 0:
				break
		return ans


import bisect

class Solution:

	def minPartition(self, N):
		arr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		while N > 0:
			idx = bisect.bisect(arr, N)
			ans.append(arr[idx - 1])
			N -= arr[idx - 1]
		return ans


class Solution:

	def minPartition(self, N):
		curr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		n = len(curr)
		ans = []
		for i in range(n - 1, -1, -1):
			while N >= curr[i]:
				N -= curr[i]
				ans.append(curr[i])
		return ans


class Solution:

	def minPartition(self, N):
		denom = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ind = len(denom) - 1
		out = []
		while N and ind > -1:
			val = N // denom[ind]
			if val:
				N -= val * denom[ind]
				out.extend([denom[ind]] * val)
			ind -= 1
		return out


class Solution:
	coins = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]

	def minPartition(self, N):
		notes = []
		coinsIdx = 0
		while N and coinsIdx < len(Solution.coins):
			noteNums = N // Solution.coins[coinsIdx]
			N = N % Solution.coins[coinsIdx]
			for i in range(noteNums):
				notes.append(Solution.coins[coinsIdx])
			coinsIdx += 1
		return notes


class Solution:

	def minPartition(self, N):
		ans = []
		l1 = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		for i in l1:
			k = N // i
			ans.extend([i] * k)
			N = N - k * i
		return ans


class Solution:

	def minPartition(self, N):
		target = N
		ar = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ar = ar[::-1]
		ans = []
		for coin in ar:
			n = target // coin
			ans.extend([coin] * n)
			target -= n * coin
			if target == 0:
				break
		return ans


class Solution:

	def minPartition(self, N):
		brr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		brr = brr[::-1]
		ans = []
		for i in range(len(brr)):
			if brr[i] <= N:
				for j in range(N // brr[i]):
					ans.append(brr[i])
				N = N % brr[i]
		return ans


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		res = []
		idx = len(coins) - 1
		while N:
			if coins[idx] <= N:
				count = N // coins[idx]
				res += [coins[idx]] * count
				N -= coins[idx] * count
			else:
				idx -= 1
		return res


class Solution:

	def minPartition(self, N):
		indian_denomination = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		coins_used = []
		for denom in reversed(indian_denomination):
			while denom <= N:
				coins_used.append(denom)
				N = N - denom
				if N == 0:
					break
		return coins_used


class Solution:

	def minPartition(self, N):
		coins_available = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		rem_money = N
		ans = []
		i = 0
		while rem_money != 0 and i < len(coins_available):
			if coins_available[i] <= rem_money:
				rem_money -= coins_available[i]
				ans.append(coins_available[i])
				if rem_money >= coins_available[i]:
					pass
				else:
					i += 1
			else:
				i += 1
		return ans


class Solution:

	def minPartition(self, N):
		lt = []
		cur = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		x = 0
		for i in range(10):
			if cur[i] > N:
				break
			x = i
		while N > 0:
			if N < cur[x]:
				x -= 1
			else:
				lt.append(cur[x])
				N -= cur[x]
		return lt


class Solution:

	def minPartition(self, N):
		d = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		res = []
		i = len(d) - 1
		while i >= 0:
			while N >= d[i]:
				N -= d[i]
				res.append(d[i])
			i -= 1
		return res


class Solution:

	def minPartition(self, N):
		currency = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		n = len(currency)
		target = N
		i = n - 1
		out = []
		while i >= 0:
			curr = currency[i]
			if target >= curr:
				target = target - curr
				out.append(curr)
			else:
				i -= 1
		return out


class Solution:

	def minPartition(self, N):
		changes = []
		while N:
			if N >= 2000:
				changes.append(2000)
				N = N - 2000
			elif N >= 500:
				changes.append(500)
				N = N - 500
			elif N >= 200:
				changes.append(200)
				N = N - 200
			elif N >= 100:
				changes.append(100)
				N = N - 100
			elif N >= 50:
				changes.append(50)
				N = N - 50
			elif N >= 20:
				changes.append(20)
				N = N - 20
			elif N >= 10:
				changes.append(10)
				N = N - 10
			elif N >= 5:
				changes.append(5)
				N = N - 5
			elif N >= 2:
				changes.append(2)
				N = N - 2
			elif N >= 1:
				changes.append(1)
				N = N - 1
		return changes


class Solution:

	def minPartition(self, N):
		coins = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		ans = []
		idx = 0
		while N and idx < len(coins):
			if coins[idx] > N:
				idx += 1
			else:
				N -= coins[idx]
				ans.append(coins[idx])
		return ans


class Solution:

	def __init__(self):
		self.res = []

	def solve(self, arr, N, summ, ct, dp):
		if summ == 0:
			self.res.append(ct)
			return 1
		if summ < 0:
			return 0
		if dp[N][summ] != -1:
			return dp[N][summ]
		if summ - arr[N - 1] >= 0:
			ct.append(arr[N - 1])
			dp[N][summ] = self.solve(arr, N, summ - arr[N - 1], ct, dp) or self.solve(arr, N - 1, summ, ct, dp)
		else:
			dp[N][summ] = self.solve(arr, N - 1, summ, ct, dp)
		return dp[N][summ]

	def minPartition(self, N):
		if N <= 0:
			return 0
		arr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		dp = [[-1 for i in range(N + 1)] for j in range(len(arr) + 1)]
		a = self.solve(arr, len(arr), N, [], dp)
		ind = 0
		if len(self.res) > 0:
			tot = sum(self.res[0])
			for i in range(1, len(self.res)):
				a = sum(self.res[i])
				if a > tot:
					tot = a
					ind = i
		return self.res[ind]


class Solution:

	def minPartition(self, N):
		arr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		curr = len(arr) - 1
		ans = []
		while N > 0:
			if arr[curr] <= N:
				ans.append(arr[curr])
				N = N - arr[curr]
			else:
				curr = curr - 1
		return ans


class Solution:

	def minPartition(self, N):
		currency = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		arr = []
		for i in currency:
			while N - i >= 0:
				arr.append(i)
				N -= i
		return arr


class Solution:

	def minPartition(self, N):
		deno = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		arr = []
		for d in deno:
			if N == 0:
				break
			while N >= d:
				arr.append(d)
				N -= d
		return arr


class Solution:

	def minPartition(self, n):
		l = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		l1 = []
		i = 0
		for i in range(10):
			while n >= l[i]:
				n = n - l[i]
				l1.append(l[i])
			i += 1
		return l1


import math

class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		s = len(coins)
		dp = [[math.inf] * (N + 1) for i in range(s + 1)]
		for i in range(1, s + 1):
			for j in range(1, N + 1):
				x = j % coins[i - 1]
				y = int(j / coins[i - 1])
				if x == 0:
					dp[i][j] = min(y, dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][x] + y
		result = []
		curr = dp[s][N]
		j = N
		while N > 0:
			for i in range(1, s + 1):
				if dp[i][j] == curr:
					x = j % coins[i - 1]
					y = int(j / coins[i - 1])
					for k in range(y):
						result.append(coins[i - 1])
					curr = curr - y
					N = x
					j = x
					break
		return result


class Solution:

	def minPartition(self, N):
		deno = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		idx = 9
		while N != 0:
			if N >= deno[idx]:
				ans.append(deno[idx])
				N -= deno[idx]
			else:
				idx -= 1
		return ans


currencies = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
num_currencies = len(currencies)

class Solution:

	def minPartition(self, N):
		i = num_currencies - 1
		taken = []
		while i >= 0 and N > 0:
			while currencies[i] <= N:
				N -= currencies[i]
				taken.append(currencies[i])
			i -= 1
		return taken


class Solution:

	def minPartition(self, N):
		notes = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		size = len(notes)
		i = size - 1
		ans = list()
		while i >= 0:
			if notes[i] > N:
				i -= 1
			else:
				N -= notes[i]
				ans.append(notes[i])
			if N == 0:
				return ans
		return ans


class Solution:

	def minPartition(self, V):
		deno = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		n = len(deno)
		ans = []
		i = n - 1
		while i >= 0:
			while V >= deno[i]:
				V -= deno[i]
				ans.append(deno[i])
			i -= 1
		return ans


class Solution:

	def minPartition(self, N):
		if N == 1:
			return [1]
		notes = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		ans = []
		for note in notes:
			cnt = N // note
			if cnt:
				for j in range(cnt):
					ans.append(note)
			N = N % note
		return ans


class Solution:

	def minPartition(self, N):
		ans = []
		arr = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		while N != 0:
			for i in range(0, 10):
				a = N // arr[i]
				N = N % arr[i]
				for j in range(a):
					ans.append(arr[i])
				if N == 0:
					break
		return ans


class Solution:

	def minPartition(self, N):
		lst = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		sum1 = []
		for i in lst:
			if i > N:
				continue
			if N == 0:
				break
			s = N // i
			N = N % i
			sum1 += s * [i]
		return sum1


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		i = 9
		while i >= 0:
			while N >= coins[i]:
				ans.append(coins[i])
				N -= coins[i]
			i -= 1
			if N == 0:
				return ans


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		i = 9
		while i >= 0:
			change = N // coins[i]
			for coin in range(change):
				ans.append(coins[i])
			if change != 0:
				N = N % (coins[i] * change)
			i -= 1
			if N == 0:
				return ans


class Solution:

	def minPartition(self, N):
		arr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		res = []
		n = len(arr) - 1
		for i in range(n, -1, -1):
			if N == 0:
				break
			while N >= arr[i]:
				N -= arr[i]
				res.append(arr[i])
		return res


class Solution:

	def minPartition(self, N):
		ans = []
		lis = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		for i in lis:
			coin = N // i
			ans += [i] * coin
			N = N % i
		return ans


class Solution:

	def minPartition(self, N):
		curr = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		i = len(curr) - 1
		ans = []
		while N != 0:
			if curr[i] <= N:
				x = N // curr[i]
				for j in range(x):
					ans.append(curr[i])
				N -= x * curr[i]
			i -= 1
		return ans


class Solution:

	def minPartition(self, N):
		result = []
		denomination = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		while N > 0:
			for i in range(len(denomination) - 1, -1, -1):
				if N >= denomination[i]:
					N = N - denomination[i]
					result.append(denomination[i])
					break
		return result


class Solution:

	def minPartition(self, N):
		result = []
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		coins.sort(reverse=True)
		while N:
			for coin in coins:
				if coin <= N:
					result.append(coin)
					N -= coin
					break
		return result


class Solution:

	def minPartition(self, N):
		coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		amount = N
		i = len(coins) - 1
		while i >= 0:
			if coins[i] <= amount:
				break
			i -= 1
		out = []
		while amount > 0 and i >= 0:
			times = amount // coins[i]
			out = out + [coins[i]] * times
			amount = amount % coins[i]
			while i >= 0:
				if coins[i] <= amount:
					break
				i -= 1
		return out


class Solution:

	def minPartition(self, N):
		dict = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []

		def help(n, ans):
			if n == 0:
				return 0
			for i in range(len(dict) - 1, -1, -1):
				if dict[i] <= n:
					ans.append(dict[i])
					n -= dict[i]
					break
			help(n, ans)
		help(N, ans)
		return ans


class Solution:

	def minPartition(self, N):
		a = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		b = 0
		c = []
		for i in range(9, -1, -1):
			while b + a[i] <= N:
				b += a[i]
				c.append(a[i])
		return c


class Solution:

	def minPartition(self, N):
		l = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		l1 = []
		for i in l:
			if i <= N:
				l1.append(i)
			else:
				break
		l1.reverse()
		s = 0
		out = []
		i = 0
		while s <= N and i < len(l1):
			if s + l1[i] <= N:
				out.append(l1[i])
				s += l1[i]
			else:
				i += 1
		return out


class Solution:

	def minPartition(self, N):
		l = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		ans = []
		for i in range(-1, -11, -1):
			if N // l[i] != 0:
				ans += [l[i]] * (N // l[i])
				N %= l[i]
		return ans


class Solution:

	def minPartition(self, N):
		den = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		den.sort(reverse=True)
		ans = []
		i = 0
		while N > 0:
			if den[i] > N:
				i += 1
				continue
			N -= den[i]
			ans.append(den[i])
		return ans


class Solution:

	def minPartition(self, N):
		currency = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		i = 0
		ans = []
		while i < len(currency):
			if currency[i] > N:
				i += 1
			elif currency[i] == N:
				ans.append(currency[i])
				return ans
			elif currency[i] < N:
				N -= currency[i]
				ans.append(currency[i])
		return ans


class Solution:

	def minPartition(self, n):
		arr = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
		ans = []
		for i in arr:
			temp = n // i
			ans += temp * [i]
			n -= temp * i
		return ans


class Solution:

	def minPartition(self, N):
		Coin = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
		Cn = 10
		ans = []
		while N > 0:
			if Coin[Cn - 1] > N:
				Cn -= 1
			else:
				ans.append(Coin[Cn - 1])
				N -= Coin[Cn - 1]
		return ans


class Solution:

	def minPartition(self, N):
		op = []

		def amt_to_be_subtracted(N):
			k = 0
			curr = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
			for note in curr:
				if note > N:
					k += 1
			return curr[k]
		while N != 0:
			minus = amt_to_be_subtracted(N)
			op.append(minus)
			N = N - minus
		return op


def dyn(v):
	coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000][::-1]
	result = []
	while v:
		for val in coins:
			if val <= v:
				result += [val] * (v // val)
				v -= val * (v // val)
	return result

class Solution:

	def minPartition(self, N):
		return dyn(N)