An employee's wallet can contain no more than M notes or coins. A boss pays his salary by the minimum notes possible. However the employee may have to leave out some money. Find how much money he has to lose if his original salary is N.
Note: The values of notes or coins available are 1000, 500, 100, 50, 20, 10, 5, 2 and 1.
Example 1:
Input:
N = 1712, M = 4
Output:
12
Explanation:
The boss will give him one 1000, one 500
and two 100 notes, one note of 10 and
one of 2. But because the employee can't
have more notes than 4, he can have a
maximum amount of 1700.
So, he will lose 12.
Example 2:
Input:
N = 1023, M = 2
Output:
3
Explanation:
The boss will give him one 1000, one 20
one 2 and one note of 1. But because the
employee can't have more notes than 2,
he can have a maximum amount of 1020.
So, he will lose 3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getLoss() which takes 2 Integers N and M as input and returns the answer.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N,M <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def getLoss(self, N, M):
        # code here

Solutions:
class Solution:

	def getLoss(self, n, m):
		notes = [1000, 500, 100, 50, 20, 10, 5, 2, 1]
		count = 0
		i = 0
		while count < m and n > 0:
			if n >= notes[i]:
				n = n - notes[i]
				count += 1
			else:
				i += 1
		return n


class Solution:

	def getLoss(self, n, m):
		t = n
		arr = [1000, 500, 100, 50, 20, 10, 5, 2, 1]
		i = 0
		while m != 0:
			while n >= arr[i]:
				n -= arr[i]
				m -= 1
				if m == 0 or n == 0:
					return n
			i += 1
		return n


class Solution:

	def getLoss(self, amount, m):
		coins = [1000, 500, 100, 50, 20, 10, 5, 2, 1]
		coins.reverse()
		cnt = []
		temp = amount
		for j in range(len(coins) - 1, -1, -1):
			while amount >= coins[j]:
				amount -= coins[j]
				cnt.append(coins[j])
		if len(cnt) <= m:
			return 0
		else:
			return temp - sum(cnt[:m])


class Solution:

	def getLoss(self, N, M):
		m = M
		while m > 0 and N > 0:
			if N // 1000 >= 1:
				v = N // 1000
				if v - m > 0:
					N -= m * 1000
					break
				m -= v
				N %= 1000
			elif N // 500 >= 1:
				v = N // 500
				if v - m > 0:
					N -= m * 500
					break
				m -= v
				N %= 500
			elif N // 100 >= 1:
				v = N // 100
				if v - m > 0:
					N -= m * 100
					break
				m -= v
				N %= 100
			elif N // 50 >= 1:
				v = N // 50
				if v - m > 0:
					N -= m * 50
					break
				m -= v
				N %= 50
			elif N // 20 >= 1:
				v = N // 20
				if v - m > 0:
					N -= m * 20
					break
				m -= v
				N %= 20
			elif N // 10 >= 1:
				v = N // 10
				if v - m > 0:
					N -= m * 10
					break
				m -= v
				N %= 10
			elif N // 5 >= 1:
				v = N // 5
				if v - m > 0:
					N -= m * 5
					break
				m -= v
				N %= 5
			elif N // 2 >= 1:
				v = N // 2
				if v - m > 0:
					N -= m * 2
					break
				m -= v
				N %= 2
			elif N // 1 >= 1:
				v = N // 1
				if v - m > 0:
					N -= m * 1
					break
				m -= v
				N %= 1
		return N