CollectingBonuses | Topcoder Archive

Problem Statement

A juice company is running a promotion where each juice bottle they sell contains a code that you can redeem for a prize. There are n different codes, each corresponding to a different type of prize. The codes are evenly distributed, so the probability of winning a certain type of prize is 1/n for each bottle. The codes are written underneath the bottle caps, so you can't read them until you buy the bottles. Your goal is to collect k different types of prizes. Return the expected number of bottles you must buy to achieve this goal.

Definition

Class:: CollectingBonuses
Method:: expectedBuy
Parameters:: String, String
Returns:: double
Method signature:: double expectedBuy(String n, String k)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

n and k will contain digits ('0' - '9') only.
n and k will represent positive integers without leading zeros.
n will represent an integer between 1 and 10^18, inclusive.
k will represent an integer between 1 and the integer n represents, inclusive.

Examples

```
"1"
```
```
"1"
```
```
Returns: 1.0
```
With only 1 type of prizes you just need to buy 1 bottle.
```
"2"
```
```
"1"
```
```
Returns: 1.0
```
Now there are 2 types of prizes, but any one will satisfy you, so you again need only 1 bottle.
```
"2"
```
```
"2"
```
```
Returns: 3.0
```
First you buy 1 bottle and collect some type of prizes. After this, you need to collect another type of prizes. Only half of bottles contains it, so in average you must buy 2 more bottles to achieve your goal.
```
"4"
```
```
"3"
```
```
Returns: 4.333333333333333
```

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.