CompleteCollection | Topcoder Archive

Problem Statement

You are collecting toys which come in colors different colors. You want to have a complete collection, i.e. at least one toy of each color. Unfortunately, you can't order a toy of specific color; when you buy a toy you get it in random color (all color have the same probabilities), and you don't know which color you'll get until the package arrives. You already have toys of have different colors. On average, how many more toys will you need to purchase to complete your collection?

Definition

Class:: CompleteCollection
Method:: expectedPurchases
Parameters:: int, int
Returns:: double
Method signature:: double expectedPurchases(int have, int colors)
(be sure your method is public)

Notes

A return value within 1e-9 absolute or relative error of the correct answer will be considered correct.

Constraints

colors will be between 1 and 100000, inclusive.
have will be between 0 and colors, inclusive.

Examples

```
0
```
```
1
```
```
Returns: 1.0
```
The toy comes in only one color, and you don't have it yet. You're guaranteed to get it on the first purchase.
```
0
```
```
2
```
```
Returns: 3.0
```
When you first buy a toy, it's guaranteed to be in a color you don't have yet. (1 purchase) After that, you have a 50/50 chance of getting the second color you need to complete the collection... You can expect to have to purchase an average of two toys to get the color you need. (2 purchases) The expected number of purchases in total is thus 3.
```
0
```
```
3
```
```
Returns: 5.5
```
Your first purchase gets you a toy in a new color. After that, each purchase has a 2/3 chance to get you a new color, thus is takes an average of 1.5 purchases to get your second unique color. Finally, it takes an average of 3 purchases to get the last color.
```
1
```
```
3
```
```
Returns: 4.5
```
Here, you already have a toy in the first color, so it's like the previous example, but step one is already complete.
```
3
```
```
3
```
```
Returns: 0.0
```
You already have the toys in all colors.
```
12345
```
```
100000
```
```
Returns: 1195838.5302859792
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.