TopCoder Statistics - Problem Statement

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

{100}

10

0

Returns: 1.0
{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.
{25,25,25,25}

15

0

Returns: 0.19805454649031162
{10,20,30,40}

10

3

Returns: 0.4970776576000002
{10,20,30,40}

15

2

Returns: 0.2315246893522561
{5,50,20,25}

15

1

Returns: 0.7947486656372071
{1,1,1,1,96}

15

4

Returns: 0.9999999999021495
{1,1,1,1,96}

15

0

Returns: 2.424064291647307E-12
{1,1,1,1,96}

15

4

Returns: 0.9999999999021495
{1,1,1,1,96}

15

0

Returns: 2.424064291647307E-12
{50, 50}

4

0

Returns: 0.3125
{20,20,20,20,20}

15

1

Returns: 0.14692899464806414
{42,40,10,1,7}

14

3

Returns: 2.7259044389006984E-7
{75,7,6,11,1}

7

2

Returns: 0.0014342498927999998
{63,3,20,1,13}

1

2

Returns: 0.2
{96,3,1}

13

1

Returns: 3.419644493461693E-8
{7,23,28,5,37}

8

3

Returns: 0.002772454379062501
{57,5,13,13,12}

12

2

Returns: 0.010514082772002166
{80,14,3,2,1}

4

3

Returns: 7.510400000000002E-4
{16,39,3,8,34}

5

2

Returns: 0.0024810678
{81,7,8,2,2}

1

1

Returns: 0.07
{3,77,8,2,10}

12

2

Returns: 2.610207193863423E-4
{30,18,20,8,24}

4

1

Returns: 0.11317967999999999
{62,38}

15

1

Returns: 0.16871538117522591
{44,24,25,5,2}

1

1

Returns: 0.24
{18,55,26,1}

9

1

Returns: 0.752181897266099
{5,23,6,6,60}

1

4

Returns: 0.6
{12,11,53,13,11}

2

2

Returns: 0.28090000000000004
{10,88,1,1}

11

3

Returns: 1.0100926426862802E-8
{64,11,22,2,1}

12

4

Returns: 2.892429036266305E-7
{36,35,20,3,6}

14

4

Returns: 7.227571893224297E-4
{4,95,1}

13

2

Returns: 8.294420989777924E-11
{52,40,6,1,1}

15

3

Returns: 1.6046989428034946E-8
{49,16,14,8,13}

15

3

Returns: 0.0019760847434884678
{31,27,1,6,35}

15

0

Returns: 0.2668795864546774
{93,5,2}

15

2

Returns: 7.461987451843091E-10
{36,1,52,5,6}

15

4

Returns: 1.316937489930609E-4
{69,3,11,5,12}

15

2

Returns: 8.537191436921399E-4
{97,3}

15

0

Returns: 0.9999999965050899
{43,47,9,1}

15

1

Returns: 0.5130442325733943
{32,59,2,1,6}

15

1

Returns: 0.8412501000215205
{59,30,8,3}

15

3

Returns: 3.8140368462496514E-6
{94,2,4}

15

1

Returns: 5.01790843745795E-10
{64,21,8,6,1}

15

4

Returns: 3.2686827995992414E-8
{62,30,1,4,3}

15

2

Returns: 1.1626912165929862E-8
{50,21,6,22,1}

15

4

Returns: 1.7370170554944125E-7
{22,66,5,5,2}

15

3

Returns: 2.770737977410473E-5
{47,29,13,7,4}

15

0

Returns: 0.7346663536178357
{96,3,1}

15

1

Returns: 3.81365619801406E-9
{40,52,7,1}

15

1

Returns: 0.6426861702482727
{61,11,15,7,6}

15

1

Returns: 0.002145028754521305
{45,7,1,8,39}

15

1

Returns: 4.448916872980047E-4

Statistics

Problem Statement for "ModeProbability"

Problem Statement

Definition

Notes

Constraints

Examples