Greedy

Counting money

Pinterest LinkedIn Tumblr

Write a program to get the amount of money and display the count of each type. The coins displays quarters, dimes, nickels, and pennies.

source Code

package com.dsacode.Algorithm.greedy;
 
public class CountingMoney {
 
    public static void main(String[] args) {
        int changeOwed = 45;
        int count = 0;
        int numQ=0, numD=0, numN=0, numP=0;
         
        System.out.println("Change owed (in cents) : "+ changeOwed);
        int c = changeOwed;
 
         
        while(c > 0){
         
            while(c >= 25){
                count ++;
                numQ++;
                c = c - 25;
            }
         
            while(c >= 10){
                count ++;
                numD++;
                c = c - 10;
            }
         
            while(c >= 5){
                count ++;
                numN++;
                c = c - 5;
            }
         
            while(c >= 1){
                count ++;
                numP++;
            c = c - 1;
            }
 
        }
        String str =    String.format("Quarters: %d, Dimes: %d, Nickels: %d, Pennies: %d\nNumber of coins used= %d\n\n", numQ, numD, numN, numP, count);
        System.out.println(str);
        
 
    }
 
}

Output

Change owed (in cents) : 45
Quarters: 1, Dimes: 2, Nickels: 0, Pennies: 0
Number of coins used= 3

Algorithm Explanation

The coins in the U.S. currency uses the set of coin values {1, 5, 10, 25}.
Total value of pennies: < 1 cent. Total value of pennies: < 5 cents.
Total value of pennies and nickels: < 10 cents.
Total value of non-quarters: < 25 cents.

Reference

  1. http://everythingcomputerscience.com/algorithms/Greedy_Algorithm.html
  2. http://www.seeingwithc.org/topic1html.html

Write A Comment