138. Cash machine
In the ATM, there
are sufficient banknotes with denominations of 10, 20, 50, 100, 200, and 500
hryvnias. Find the minimum number of banknotes needed to dispense the amount of
n hryvnias.
Input. One integer n (1 ≤ n ≤ 106).
Output. Print the minimum number of banknotes needed to dispense n hryvnias. Print -1 if the
specified amount cannot be dispensed.
Sample input |
Sample output |
770 |
4 |
greedy
Take a banknote of the maximum denomination c available and use it
to dispense the
amount n as long as possible. The maximum number of such banknotes that can be dispensed is n / c. The remainder n % c hryvnias are dispensed using other denominations.
Example
The amount of 770 hryvnias can be dispensed as
follows: 500 + 200 + 50 + 20.
Store the denominations of available
banknotes in the
array ñ.
int c[6] = { 500, 200, 100, 50, 20, 10 };
Read
the input value of n.
scanf("%d", &n);
In the variable res count the
number of dispensed banknotes.
res = 0;
Iterate through the available six denominations of banknotes. To
dispence the amount n, use a maximum
of n / c[i] banknotes with a denomination of c[i]. After using the denomination c[i], the remaining amount is
equal to n % c[i].
for (i = 0; i < 6; i++)
{
res += n / c[i];
n = n % c[i];
}
If
the total sum is dispensed (n = 0), then print the found number of banknotes res. Otherwise
print -1.
if (n > 0) printf("-1\n"); else printf("%d\n", res);
Java implementation
import java.util.*;
public class Main
{
static int c[] = {500, 200,
100, 50, 20, 10};
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
int res = 0;
for(int i = 0; i < 6; i++)
{
res += n / c[i];
n = n % c[i];
}
if (n > 0)
System.out.println("-1");
else
System.out.println(res);
con.close();
}
}
Python implementation
Read
the input value of n.
n = int(input())
In the variable res count the
number of dispensed banknotes.
res = 0
Store the denominations of available
banknotes in the
list ñ.
c = [500, 200, 100, 50, 20, 10]
Iterate through the available six denominations of banknotes. To
dispence the amount n, use a maximum
of n / c[i] banknotes with a denomination of c[i]. After using the denomination c[i], the remaining amount is
equal to n % c[i].
for i in range(6):
res += n // c[i]
n %= c[i]
If
the total sum is dispensed (n = 0), then print the found number of banknotes res. Otherwise
print -1.
if n > 0:
print("-1")
else:
print(res)