ModeProbability
TCO05 Semi 3 · 2005-08-16 · by AdminBrett
TCO05 Semi 3 · 2005-08-16 · by AdminBrett · Advanced Math
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.
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
0)
{100}
10
0
Returns: 1.0
1)
{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.
2)
{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.
3)
{25,25,25,25}
15
0
Returns: 0.19805454649031162
4)
{10,20,30,40}
10
3
Returns: 0.4970776576000002
Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ModeProbability with a public method double getProb(vector<int> probs, int n, int value) · 53 test cases · 2 s / 256 MB per case