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

 

 

SOLUTION

greedy

 

Algorithm analysis

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.

 

Algorithm implementation

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)