a Programmer's blog

import java.util.Collections;
import java.util.Stack;

class runner
{
	static final int[] available = new int[] {1,2,5,10,20,50,100,200}; 

	private static int counting(int m){
		Stack tally = new Stack< Integer>();
		//setup
		setupTally(m, tally);

		int count = 1+counting_aux(tally);

		return count;
	}
	private static int counting_aux(Stack tally){
		if(tally.size() == 0 || tally.firstElement() == 1) return 0;

		int count = 0;

		int prev = tally.lastElement();
		Stack temporaryTally = new Stack();
		for(int i=tally.size()-1; i>-1; i--){
			if(prev < tally.get(i))
				temporaryTally = subList(tally, i+1, tally.size());
			switch(tally.get(i)){
			case 200: 	temporaryTally.push(100);temporaryTally.push(100);
			break;
			case 100:	temporaryTally.push(50);temporaryTally.push(50);   
			break;
			case 50: 	temporaryTally.push(20);temporaryTally.push(20);
						if(temporaryTally.contains(10)){
							temporaryTally.remove(temporaryTally.indexOf(10));
							temporaryTally.push(20);
						}else 
							temporaryTally.push(10);
			break;
			case 20: 	temporaryTally.push(10);temporaryTally.push(10);
						break;
			case 10: 	temporaryTally.push(5);temporaryTally.push(5);
			break;
			case 5: 	temporaryTally.push(2);temporaryTally.push(2);
						if(temporaryTally.contains(1)){
							temporaryTally.remove(temporaryTally.indexOf(1));
							temporaryTally.push(2);
						}else 
							temporaryTally.push(1);
			break;
			case 2: 	temporaryTally.push(1);temporaryTally.push(1);
			break;
			}
			reOrder(temporaryTally);

			if(tally.get(i) != 1) count++;

			count += counting_aux(temporaryTally);
			prev = tally.get(i);
		}

		return count;
	}

	private static Stack subList(Stack tally, int from, int to){
		Stack x = new Stack();
		if(from > tally.size() || to > tally.size()) return x;
		for(int i = from; i tally){
		int i = available.length-1;
		while(i>=0){
			if(m >= available[i]){
				m -= available[i];
				tally.push(available[i]);
			}else{
				i--;
			}
		}
	}
	private static void reOrder(Stack tally){
		Collections.sort(tally);
		Collections.reverse(tally);
	}

	private static void test(int i, int r){
		int actual = counting(i);
		System.out.println((actual == r)+"\t:: Testing i:"+i+" r:"+r+" actual:"+actual);
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();

		test(1,1);//1
		test(2,2);//2, 11
		test(3,2);//21, 111
		test(4,3);//22, 211, 1111
		test(5,4);//5, 221, 2111, 11111
		test(6,5);//51, 222, 2211, 21111, 111111
		test(10,11);//A, 55, 5221, 521*3, 51*5, 22222, 222211, 2221*4, 221*6, 21*8, 1*A
		test(11,12);//A1, 551, 5222, 52211, 521*4, 51*6, 222221, 22221*3, 2221*5, 221*7, 21*9, 1*B
		test(12,15);//A2, A11, 552, 52221, 522111, 5211111, 51111111, 222222, 2222211, 22221*4, 2221*6, 221*8, 21*A, 1*C
		
		System.out.println(counting(200));

		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}