ModeProbability | Topcoder Archive

Problem Statement

You have a skewed random number generator that outputs the number i with percentage probs[i]. Given that you have generated n numbers, return the probability (between 0 and 1) that value has been generated more times than any of the other numbers.

Definition

Class:: ModeProbability
Method:: getProb
Parameters:: int[], int, int
Returns:: double
Method signature:: double getProb(int[] probs, int n, int value)
(be sure your method is public)

Notes

The returned value must be accurate to 1e-9 relative or absolute.

Constraints

probs will contain between 1 and 5 elements inclusive.
Each element of probs will be between 1 and 100 inclusive.
The elements of probs will sum to 100.
n will be between 1 and 15 inclusive.
value will be between 0 and N-1 inclusive, where N is the number of elements in probs.

Examples

```
{50,50}
```
```
2
```
```
0
```
```
Returns: 0.25
```
Two equally occurring numbers. For 0 to occur more than 1 it needs to be generated twice in a row. Hence, the probability is 1/4.
```
{50,50}
```
```
9
```
```
0
```
```
Returns: 0.5
```
Since we generate 9 numbers, one number will always occur more times than the other. By symmetry, 0 occurs more frequently with probability 1/2.

{5,50,20,25}

Returns: 0.7947486656372071

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.