CareerCup

1. Calculate the Payment-Cost, say X
2. Start dividing X with largest denomination and pay the remainder number of denominations. X = X - (Remainder no. * denomination)
3. Repeat step 2 until X == 0

Say cost is 75 cents
Payment done is 10$
X = 9.25
X % 10 = 0 ( 0 * 10)
X % 5 = 1 (1 * 5) X = 9.25 - 5 = 4.25
X % 1 = 4 (4 * 1) X = 4.25 - 4.00 = .25
X % 25 = 1 (1 * .25) X = .25 - .25 = 0
X == 0

No need for checking 10$. Obviously since 10$ is the maximum denomination accepted and assuming the customer purchases something...the cashier cannot give 10$ back.

public class Denomination {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		double amountPaid;
		double itemCost, amountReturned;
		int index = 0;
		double denominations[] = {10, 5, 1, .25, .1, .05, .01};
		itemCost = .5;
		amountPaid = 5;
		amountReturned = amountPaid - itemCost;
		System.out.println("Return a total of $" + amountReturned + ".");
		while(amountReturned > 0) {
			int num_denominations = (int) (amountReturned/denominations[index]);
			amountReturned = amountReturned - (num_denominations*denominations[index]);
			System.out.println("Number of $" + denominations[index] + " to be returned: " + num_denominations);
			index++;
		}
	}

}

Using greedy algorithm can solve this problem easily.

//take input cost as float cost_f
//multiply by 100 to and cast to int
cost_i = (int) (cost_f*100) //100 since 1c (1/100 of $1) is least
//repeatedly divide by domination *100 to get respective values
tens = cost_i/(10*100); modulo_ten = cost_i%(10*100);
fives = modulo_ten/(5*100); modulo_five = modulo_ten%500;
//and so on.. till one_cents

Dynamic programming solution appears to be the optimal one.

/*
At a geeks goodies store.. every thing is either one dollar or less. and they accept only 10 dollars or less than 10 as denominations.So make a function that takes in the cost and payment as input and that out puts the change.
The denominations are namely 1c,5c,10c,25c,$1,$5,$10.
*/
#include<iostream>
using namespace std;

float coins[]={5,2,1,0.25,0.10,0.05,0.01};
#define TOTALCOINS 7

void coin_change(float cost,float payment)
{
	if (payment<0.01 || cost<0.01){cout<<"Ivalid Input";}
	else if (payment>10){cout<<"We only accept denominations upto 10 dollars \n";}
	else if (cost>payment){cout<<"Payment is less than the cost. Please give $"<<cost<<endl;}
	else if (cost==payment){cout<<"Payment complete. Thank you for visit.\n";}
	else
	{
		int num_of_coins[TOTALCOINS]={0};
		float to_return=payment-cost;
		int index=0,c=0;
		while (to_return>0 && index<TOTALCOINS)
		{
			c=(int)(to_return/coins[index]);
			num_of_coins[index]=c;
			to_return=to_return-(c*coins[index]);
			index++;
		}
		for(int i=0;i<TOTALCOINS;i++)
		{
			cout<<"Number of $"<<coins[i]<<" coins= "<<num_of_coins[i]<<endl;
		}
	}
}

int main()
{
	float cost,payment;
	cout <<"Enter the cost\n";
	cin>>cost;
	cout<<"Enter the payment\n";
	cin>>payment;
	coin_change(cost,payment);
	
}

Python working code

"""
12:50
@Python 2.7
At a geeks goodies store.. every thing is either one dollar or less. and they accept only 10 dollars or less than 10 as denominations.So make a function that takes in the cost and payment as input and that out puts the change. 
The denominations are namely 1c,5c,10c,25c,$1,$5,$10

- rohith on May 11, 2010 Report Duplicate | Flag 
"""

class CoinChange(object):
  def __init__(self, payment, cost):
    if payment is None or cost is None:
      print 'invalid inputs'
      raise SystemExit
      
    self._payment = payment * 100
    self._cost = cost * 100
    self._coins = [1000, 500, 100, 25, 10, 5, 1]
    
  def getChange(self):
    total = self._payment - self._cost
    pos = 0
    while total > 0:
      # print total, '/', self._coins[pos]
      tmp = int(total // self._coins[pos])
      # print 'tmp = ', tmp
      total = total - tmp * self._coins[pos]
      print str(tmp) + ' X $' + str(self._coins[pos] / 100.0)
      pos += 1
      
if __name__ == '__main__':
  cc = CoinChange(10, 0.15)
  cc.getChange()