ExpectedBalls | Topcoder Archive

Problem Statement

You have N balls and N buckets. Independently, and uniformly at random, you place the balls in the buckets. Given 1 <= N <= 10, return the expected number of balls that will end up in the bucket with the most balls out of any bucket.

Definition

Class:: ExpectedBalls
Method:: expected
Parameters:: int
Returns:: double
Method signature:: double expected(int N)
(be sure your method is public)

Constraints

N will be between 1 and 10, inclusive.

Examples

```
1
```
```
Returns: 1.0
```
The one ball always ends up in the one bucket.
```
2
```
```
Returns: 1.5
```
Half the time the two balls end up in the same bucket, half the time they end up in different buckets.
```
3
```
```
Returns: 1.8888888888888893
```
The following table shows all the possible outcomes for the three buckets, along with the probabilities: outcome | probability --------+----------- 0 0 3 | 1/27 0 1 2 | 1/9 0 2 1 | 1/9 0 3 0 | 1/27 1 0 2 | 1/9 1 1 1 | 2/9 1 2 0 | 1/9 2 0 1 | 1/9 2 1 0 | 1/9 3 0 0 | 1/27 The expected value is thus: 3 * (1/9) + 2 * (6/9) + 1 * (2/9) = 17/9

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.