Problem Statement
You are interested in purchasing a colleciton of items. Sadly, they are only sold as "blind bags" where you do not know which item you will receive until you open it. The frequency of receiving each type of item is given in
Given that each item you receive is selected at random according to the given frequency, and that you will continue purchasing items until you have one of each, what is the averge number of purchases you will expect to make to have a complete collection?
Definition
- Class:
- RareItems
- Method:
- expectedPurchases
- Parameters:
- int[]
- Returns:
- double
- Method signature:
- double expectedPurchases(int[] frequency)
- (be sure your method is public)
Constraints
- frequency will contain between 1 and 20 elements, inclusive.
- Each element of frequency will be between 1 and 1000, inclusive.
Examples
{1}
Returns: 1.0
There is only one item, so on your first purchase, you complete your collection.
{2,2}
Returns: 3.0
On your first purchase, you get an item you don't yet have. On your second purchase, one of two things happens (with equal probability): you either get the item you need (and thus complete your colleciotn), or else get the same item you already have, and then have to keep buying.
{1,1,100}
Returns: 153.00019801980199
Like many collectibles, getting the rare item can take a while.
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Returns: 263.58466676215386
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 71.9547931428736
{1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 19001.13451575775
{97,802,370,378,504,853,730,818,829,621,546,410,128,428,954,935,340,270,436,676}
Returns: 166.50782300858137
{610,878,119,869,750,43,741,374,641,277,492,869,996,532,230,964,658,247,76,708}
Returns: 329.5567160639591
{154,940,431,650,78,678,321,803,141,407,404,471,426,208,802,219,684,502,629,461}
Returns: 170.74948428438623
{112,357,177,552,129,677,414,597,199,990,278,93,194,728,522,670,448,469,791,72}
Returns: 196.4556795996297
{723,938,234,235,874,22,443,789,730,11,281,157,619,615,597,797,763,880,521,401}
Returns: 1129.0706564008772
{265,725,605,151,130,311,277,698,686,132,772,215,711,557,739,174,124,943,679,108}
Returns: 172.6415653971659
{235,626,867,188,710,121,475,580,132,725,907,569,949,390,808,998,334,83,106,563}
Returns: 212.85436170397838
{746,745,104,598,240,67,446,62,876,423,674,821,202,414,167,640,859,417,442,9}
Returns: 1028.1930011504273
{837,698,567,961,225,203,266,322,750,742,841,41,837,116,362,490,522,269,949,644}
Returns: 296.3379636833321
{675,413,704,709,52,87,368,535,224,169,140,918,642,97,726,49,179,143,374,37}
Returns: 316.68305763499853
{2, 2 }
Returns: 3.0
{1, 2, 109 }
Returns: 130.66699877525565
{1, 1, 100 }
Returns: 153.00019801980199