Problem Statement
A common selling trick for collectibles is the "blind box" format, in which there are multiple different designs for a certain collectible. The outer packaging of the collectible does not indicate which design will be inside. Thus, collecting a complete set of designs means that a little bit of luck and persistence is required. And getting all the designs will often involve getting several duplicates as well, which is precisely the point of this selling trick.
You want to collect numSets complete sets of designs of one particular collectible. There are numItems different designs. You are purchasing the collectibles one at a time, and each purchase will yield a design chosen uniformly at random. What is the expected total number of purchases you will make until you collect at least numSets copies of each design?
Definition
- Class:
- BlindBoxSets
- Method:
- expectedPurchases
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double expectedPurchases(int numSets, int numItems)
- (be sure your method is public)
Notes
- Returned value must be within 1e-9 absolute or relative error of the reference output to be considered correct.
Constraints
- numSets will be between 1 and 4, inclusive.
- numItems will be between 1 and 50, inclusive.
Examples
1
1
Returns: 1.0
There is exactly one item, and you want one set of it. If you buy an item, you're guaranteed to get the one you're looking for.
1
2
Returns: 3.0
There are two different designs and you want to have both of them. If you are lucky, two purchases are enough but sometimes you will need more. For example, with probability 1/8 the second and the third box you'll purchase will contain the same design as the first box, and only the fourth box will yield the other design. On average, you will need to purchase exactly three boxes.
2
1
Returns: 2.0
Since there's only one unique design, simply buying two items gets you two "complete sets".
2
2
Returns: 5.5
After we buy two items, we have an even chance of either of two scenarios: We already have two copies of the same design and we need two copies of the other. On average, this requires four more purchases. We already have one copy of each design and we need one more copy of each design. This is the same situation as in Example #1 and thus on average it requires three more purchases. So, on average, we need 2 + (4+3) / 2 = 5.5 total purchases.
4
50
Returns: 492.7090346619561
4
1
Returns: 4.0
4
30
Returns: 274.35686351658876
4
47
Returns: 459.14832250432494
3
9
Returns: 53.95589465665629
2
49
Returns: 317.1633858783798
1
13
Returns: 41.34173881673882
3
12
Returns: 76.56409514471378
1
27
Returns: 105.06933233780617
4
9
Returns: 66.6637002073772
3
20
Returns: 141.10434464891668
2
8
Returns: 34.88468682323812
2
7
Returns: 29.424741036102375
4
5
Returns: 32.602793963549864
2
46
Returns: 294.40215312625566
2
46
Returns: 294.40215312625566
3
43
Returns: 345.9288574108666
4
42
Returns: 403.7847104661126
2
10
Returns: 46.22957063944816
4
18
Returns: 151.56023250293708
2
34
Returns: 205.74312717150093
3
48
Returns: 392.8825450726018
3
23
Returns: 166.46963447585821
3
45
Returns: 364.6285931011397
3
50
Returns: 411.8479001455821
2
3
Returns: 9.63888888888889
3
47
Returns: 383.4381224325449
3
41
Returns: 327.344164835548
3
25
Returns: 183.65827712278121
4
33
Returns: 306.1966622733495
4
20
Returns: 171.4201726247379
4
48
Returns: 470.3079321027056
4
40
Returns: 381.8550775637601
4
4
Returns: 24.71023253491392
3
2
Returns: 7.875
3
10
Returns: 61.36613952234992
2
50
Returns: 324.7972682322548
1
50
Returns: 224.96026691647114
4
46
Returns: 448.01680454021783
2
24
Returns: 135.5337120684079
4
21
Returns: 181.45420896079145
4
49
Returns: 481.4950291623892