I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Change Calculator

01.24.2013
| 5063 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Determine the minimum number of coins for change

Given any number between 1 and 99, determine how to give change with the minimum number of coins. You can assume that the coins are 1c, 2c, 5c, 10c, 20c and 50c.


Catch up on all our previous puzzlers here.

 

Comments

sun east replied on Thu, 2013/01/24 - 6:14am

 Scala:


def change(m: Int, cs: List[Int] = 50::20::10::5::2::1::Nil):
    List[Int] = cs match {
    case Nil   => Nil
    case x::rs => List.fill(m/x)(x):::change(m%x, rs)
  }

scala> change(50)
res1: Seq[Int] = List(50)

scala> change(33)
res2: Seq[Int] = List(20, 10, 2, 1)

scala> change(99)
res3: Seq[Int] = List(50, 20, 20, 5, 2, 2)

Thomas Mueller replied on Thu, 2013/01/24 - 8:13am

Java:
List<Integer> list = new ArrayList<Integer>();
for (int c : new int[] { 50, 20, 10, 5, 2, 1 }) {
    for (; x >= c; x -= c) list.add(c);
}

Benedikt Lind replied on Thu, 2013/01/24 - 8:33am

Java


public void determineCoinCount(int sum) {
		if(sum > 0) {
			if(sum % 50 >= 0 && sum >= 50) {
				this.counter50++;
				determineCoinCount(sum-50);
			} else if(sum % 20 >= 0 && sum >= 20) {
				this.counter20++;
				determineCoinCount(sum-20);
			} else if(sum % 10 >= 0 && sum >= 10) {
				this.counter10++;
				determineCoinCount(sum-10);
			} else if(sum % 5 >= 0 && sum >= 5) {
				this.counter5++;
				determineCoinCount(sum-5);
			} else if(sum % 2 >= 0 && sum >= 2) {
				this.counter2++;
				determineCoinCount(sum-2);
			} else if(sum % 1 >= 0 && sum >= 1) {
				this.counter1++;
				determineCoinCount(sum-1);
			}
		}
	}

ebenezer raj replied on Thu, 2013/01/24 - 10:27am


 

{
  f:{
  c:(50;20;10;5;2;1);
  a:max c where c <=x[0];
  x[2]:x[0] div a;
  x[0]:x[0] mod a;
  x[1]:a;
  x
  };

  a:reverse 1_reverse 1_f scan (x,2#0);
  a:flip a[;1],'a[;2];
  a

}99

 

prints (50 20 5 2i;1 2 1 2i)

 

Alex Oscherov replied on Thu, 2013/01/24 - 12:13pm

 It looks to me that proposed here solutions are in general incorrect. Let's assume that set of coins is different 1c, 10c, 15c, 20c. Than for change(29) you will produce {20,1,1,1,1,1,1,1,1,1} -  10 coins while obviously there is a better solution {15, 10, 1,1,1,1} - 6 coins

Thomas Mueller replied on Thu, 2013/01/24 - 2:06pm in response to: Alex Oscherov

Alex, you are right for a different coin set, but according to the article "You can assume that the coins are 1c, 2c, 5c, 10c, 20c and 50c." Do the proposed solutions give the wrong result with those coins?

Honey Monster replied on Fri, 2013/01/25 - 9:32pm

Solution in C#

Func<int, IEnumerable<int>> change = amt => new[] {50, 20, 10, 5, 2, 1}
    .SelectMany(coin => Enumerable.Repeat(coin, Math.DivRem(amt, coin, out amt)));

CollectionAssert.AreEqual(new[] {20, 10, 5, 2, 2}, change(39).ToList());

Alex Oscherov replied on Thu, 2013/01/24 - 6:31pm in response to: Thomas Mueller

 You are right I didn't read carefully enough. Also finding algorithm for generic set of coins looks like much more challenging problem

jeroen dijkmeijer replied on Fri, 2013/01/25 - 2:01am

Alex is right: with his misreading it becomes more of a challenge. Maybe for next week?

Remigio Di Muzio replied on Fri, 2013/01/25 - 2:08am

Seems that all proposed algorithms work for sets of n coins with the following property:


for each c(i) i = 2,...,n c(1)+...+c(i-1) < c(i)

Vijay Nathani replied on Fri, 2013/01/25 - 2:19am

Groovy solution

def findCoinsFor(int amount) {
	[50, 20, 10, 5, 2, 1].inject(new LinkedHashMap()) { acc, coin ->
		int number = amount / coin
		if (number) { acc.put (coin, number); amount -= coin * number }
		acc
	}
}
assert findCoinsFor(39) == [20:1, 10:1, 5:1, 2:2]

Rajesh Pitty replied on Fri, 2013/01/25 - 2:47am

in Scala

def countChange(money: Int, coins: List[Int]): Int = (money, coins) match {
  case (0, _) => 1
  case (x, c) if ((x < 0) || c.isEmpty) => 0
  case _ => countChange(money - coins.head, coins) + countChange(money, coins.tail)
 }

Charl Victor replied on Fri, 2013/01/25 - 9:44am

Could probably refactor a bit to get cleaner/shorter, but it works :)

Java:

 @Test
    public void calculateChange() {

        int originalChange = 99;
        Set<Integer> coinSet = new LinkedHashSet<Integer>();

        coinSet.add(50);
        coinSet.add(20);
        coinSet.add(10);
        coinSet.add(5);
        coinSet.add(2);
        coinSet.add(1);

        Map<Integer, Integer> selectedCoins = new LinkedHashMap<Integer, Integer>();

        int balance = originalChange;
        for (Integer coin : coinSet) {
            int times = balance / coin;
            if (times > 0)
            {
                selectedCoins.put(coin, times);
            }
            balance = balance - (coin*times);
        }

        System.out.println("Change: " + originalChange);
        System.out.println("Coins: " + selectedCoins);
    }

Vijay Nathani replied on Fri, 2013/01/25 - 10:16am in response to: Charl Victor

Consider making coinset an array.

Line numbers 05 to 12 can be changed to a single line

Integer[] coinset =  {50,20,10,5,2,1};

Charl Victor replied on Mon, 2013/01/28 - 3:02am in response to: Vijay Nathani

Will give it a try, thanks.

Sriram Yadla replied on Wed, 2013/01/30 - 10:04am

Java
public void changeCalculator (int money) {
final int arr[] = { 50, 20, 10, 5, 2, 1 } ;
for (int j = 0; j < arr.length; j++) {
if (money / arr[j] > 0) {
System.out.println(arr[j] + "c - " + money / arr[j]) ;
money = money % arr[j] ;
}
}
}

Suresh Thallam replied on Wed, 2013/01/30 - 11:06am

public void calculateChange(int x){
int coins[] = { 50,25,10,5,1 };

for(int i=0; ;i++){
while(x >= coins[i]){
 System.out.println("Coins: "+coins[i]);
 x=x-coins[i];
}
if(x==0) break;
}
}


Knut W. Hansson replied on Thu, 2013/01/31 - 5:00am

 I'm impressed with Alex Oscherow pointing out a poosible flaw in the suggested algorithms, and perhaps even more impressed with Remigio Di Muzio's property that makes them work correctly.

It seems to me that most note and coin systems I know follow the rules of Di Muzio's property, which is probebly not a coincidence. Most notes/coins are on the principle that the next lower denomination is half or less of the one above. I think this actually is another way of fomulating the principle.

Thus, solving the problem for any arbitrary set of coins does not seem like a practical problem.


Nicole Johnson replied on Thu, 2013/01/31 - 6:05am

C++

   int c; //change
   int cp; //change place holder
   int np = 0; //number of coins place holder
   int n = 0; //number of coins
   int d = 1; //denomination
   int da; //denomination amount

   switch (d)

     {
       case 1: da = 50;
       break;
       case 2: da = 20;
       break;
       case 3: da = 10;
       break;
       case 4: da = 5;
       break;
       case 5: da = 2;
       break;
       case 6: da = 1;
       break;
       default: cout << "error";
         
     }

   cp = c;

   
       
     if ((c!= 0) && (c> 0) && (c <= 100))     
       {
         while ((cp!=1) && (cp > 0) && (d < 6))
           {   
             
             
             if ((d != 6) || (da <= c))
               {   
                 
                 np = cp/da;
               
                 cp = cp - (np * da);
                 
                 n = n + np;
             
                 
                 d++;
                 

                     if (cp == 1)
                       n = n+1;
                 
                     
                 switch (d)

                   {
                     case 1: da = 50;
                     break;
                     case 2: da = 20;
                     break;
                     case 3: da = 10;
                     break;
                     case 4: da = 5;
                     break;
                     case 5: da = 2;
                     break;
                     case 6: da = 1;
                     default: cout << "error" << endl;
         
                   }
               }

               

             else
                 d++;
     
   

   

   

 

Diego Pettisani replied on Fri, 2013/02/01 - 3:01am

This is a general method that resolves the problem in Java:

	public static void main(String[] args) {
		// input values of the method
		int value = 89;
		int[] coins = new int[] { 50, 20, 10, 5, 2, 1 }; 
		
		int[] coinsCount = getChange(coins, value);
		System.out.println("Coins for " + value + "c:");
		for (int i=0; i<coins.length; i++) {
			System.out.println("#" + coins[i] + "c: " + coinsCount[i]);
		}
	}
	
	public static int[] getChange(int [] coins, int value) {
		int[] result = new int[coins.length];
		int remaining = value;
		for (int i=0; i<coins.length && remaining > 0; i++) {
			result[i] = remaining / coins[i];
			remaining %= coins[i];
		}
		return result;
	}
	


It will output:

Coins for 89c:
#50c: 1
#20c: 1
#10c: 1
#5c: 1
#2c: 2
#1c: 0

Only one constraint: the coins array of the getChange method must have a descending order.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.