/** Recently quarters have been minted for each state.
    Assume that there are N (say 50) different kinds of quarters
    in circulation, and that when I get a quarter its kind could be any of 
    the N possible, with equal probability.
    Question: How many quarters on average I will need to get before I can 
    collect all N quarters? It tells that the average is 224.93913
*/

public class AllQuarters
{
    public static final int NUMBER_OF_QUARTERS = 50;
    public static final int NUMBER_OF_TRIES = 100000;

    public static int nextQuarter() {
	return (int)(NUMBER_OF_QUARTERS*Math.random());
    }

    public static void main(String[] args) {
	int sum = 0;
	for (int k = 0; k < NUMBER_OF_TRIES; k++) {
	    int[] quarters = new int[NUMBER_OF_QUARTERS];
            int collected = 0;
  	    int n = 0;
	    while(true) {
		n++;
		int w = nextQuarter();
		if (quarters[w] == 0) {
		    quarters[w] = 1;
		    collected++;
		    if (collected == NUMBER_OF_QUARTERS) break;
		}
	    }
	    sum += n;
	}
	System.out.println("The average number of quarters is " +
		(double)sum/NUMBER_OF_TRIES);
    }
}