public class CouponCollector {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]); // number of card types
boolean[] found = new boolean[N]; // found[i] = true if card i has been collected
int cardcnt = 0; // total number of cards collected
int valcnt = 0; // number of distinct cards
// repeatedly choose a random card and check whether it's a new one
while (valcnt < N) {
int val = (int) (Math.random() * N); // random card between 0 and N-1
cardcnt++; // we collected one more card
if (!found[val]) valcnt++; // it's a new card type
found[val] = true; // update found[]
}
// print the total number of cards collected
System.out.println(cardcnt);
}
}
/*************************************************************************
* Given N distinct card types, how many random cards do you need
* do collect before you have (at least) one of each type?
* This program simulates this random process.
*
*
* % java CouponCollector 1000
* 6583
*
* % java CouponCollector 1000
* 6477
*
* % java CouponCollector 1000000
* 12782673
*
*************************************************************************/
Not Satisfied ? Just search & get the result
Related posts:
