CareerCup

#include <iostream>
#include <vector>

#include <cassert>

using namespace std;

int main(int argc, char** argv) {

  cout << "Enter a total amount to make, in cents" << endl; // to ensure whole numbers
  int total; // ought to not use floating point for currency, but for practical purposes lets just use it.
  cin >> total;
  // Assume number is OK (i.e. there are no more than 2 decimal places, it is not negative, etc)

  if(total < 0) {
    cerr << "cannot have a negative total!" << endl;
    return 1;
  }

  cout << "total: " << total << endl;
  vector<int> coin_values = {25, 10, 5, 1};  // to find the minimal number of coins,
                                                  // this list must be in descending order
  vector<int> coins_needed;
  for(auto v : coin_values) {
    unsigned int need = total / v;
    total -= need * v;
    coins_needed.push_back(need);
  }

  assert(coin_values.size() == coins_needed.size());
  for(auto i = 0; i < coin_values.size(); ++i) {
    cout << "Number of " << coin_values[i] << " cent coins needed: " << coins_needed[i] << endl;
  }
  return 0;
}

import java.util.HashMap;
import java.util.Map;

public class Q3 {

	static int a[] = { 25, 10, 6, 1 };
	//the coin value to number of occurrence. example for 112 you get {6=2, 25=4}
	static Map<Integer, Integer> smallestCandidate = new HashMap<Integer, Integer>();

	public static void main(String[] args) {
		permuteCoins(112, new HashMap<Integer, Integer>(), 0);
		System.out.println(smallestCandidate);
		smallestCandidate.clear();

		permuteCoins(36, new HashMap<Integer, Integer>(), 0);
		System.out.println(smallestCandidate);
		smallestCandidate.clear();

		permuteCoins(47, new HashMap<Integer, Integer>(), 0);
		System.out.println(smallestCandidate);
		smallestCandidate.clear();
	}

	/**
	 * find all possible combinations of coins that adds to the a given number
	 * 
	 */
	private static void permuteCoins(int number,
			Map<Integer, Integer> currentResult, int index) {
		if (number <= 0) {
			// Compare the current combination of coins of the smallest
			// candidate
			if (smallestCandidate.isEmpty()
					|| getSize(smallestCandidate) > getSize(currentResult)) {
				smallestCandidate.clear();
				smallestCandidate.putAll(currentResult);
			}
			return;
		}
		for (int i = index; i < a.length; i++) {
			if (a[i] <= number) {
				int numOfCoin = number / a[i];
				Map<Integer, Integer> thisResult = new HashMap<Integer, Integer>(
						currentResult);
				thisResult.put(a[i], numOfCoin);
				permuteCoins(number % a[i], thisResult, i + 1);
			}
		}
	}

	private static int getSize(Map<Integer, Integer> r) {
		int size = 0;
		if (!r.isEmpty()) {
			for (Integer v : r.values()) {
				size += v;
			}
		}
		return size;
	}
}

The above seems so complicated for this question? Maybe I misunderstood the question but heres mine:

public class CoinCounter{

public static void main(String []args){
System.out.println("Hello World");

countCoin(126);
}

private static void countCoin(int n) {
int quarters, dimes, nickels, pennies;

quarters = n / 25;
n = n - (quarters * 25);
dimes = n / 10;
n = n - (dimes * 10);
nickels = n / 5;
n = n - (nickels * 5);
pennies = n;

print("quarters:" + quarters +
", dimes:" + dimes +
", nickels:" + nickels +
", pennies:" + pennies);
}

private static void print(String s) {
System.out.println(s);
}

private static void print(char c) {
System.out.print(String.valueOf(c));
}
}

int[] coins = {25,10,6,1};

int mainFunction(int change)
{
   return MinCoin(change, 0);
}

int MinCoin(int change, int count)
{
   if(change<=0) return count;
   int min = INT_MAX;
   for(int i=0;i<coins.length;++i)
   {
          if(change>=coins[i])
	  {
	      int c = MinCoin(change-coins[i], count+1);
	      min = Min(c, min);
      }
   }
   
   return min;
}

A pretty simple dp algorithm:

sub dp_count_coins {
   my ($sum, @denoms) = @_;

   # initialize dp table to length of $sum + 1, set all elements to 999 (i.e. not a low number)
   my @dp_table = (999) x ($sum + 1);

   # starting solution, there are 0 ways to count a 0 cents
   $dp_table[0] = 0;

   foreach my $i ( 1 .. $sum ) {
      foreach my $j ( 0 .. $#denoms ) {
         if ( $i >= $denoms[$j] && 1 + $dp_table[$i - $denoms[$j]] < $dp_table[$i] ) {
            $dp_table[$i] = 1 + $dp_table[$i - $denoms[$j]]
         }
      }
   }

   return $dp_table[$sum];
}