KthProbableElement | Topcoder Archive

Problem Statement

M integers are randomly independently chosen from the interval lowerBound...upperBound, inclusive. Return the probability that the K-th smallest element of the generated set is equal to N. K=1 refers to the smallest element, K=2 refers to the second smallest element, and so on.

Definition

Class:: KthProbableElement
Method:: probability
Parameters:: int, int, int, int, int
Returns:: double
Method signature:: double probability(int M, int lowerBound, int upperBound, int N, int K)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

M will be between 1 and 100, inclusive.
lowerBound will be between 1 and 1000, inclusive.
upperBound will be between lowerBound and 1000, inclusive.
N will be between lowerBound and upperBound, inclusive.
K will be between 1 and M, inclusive.

Examples

```
1
```
```
1
```
```
10
```
```
3
```
```
1
```
```
Returns: 0.1
```
The probability that the only chosen number will be equal to 3 is 0.1.
```
3
```
```
1
```
```
2
```
```
2
```
```
2
```
```
Returns: 0.5
```
There are 8 ways to choose 3 numbers from the interval 1..2: Numbers | 2nd smallest element 1 1 1 | 1 1 1 2 | 1 1 2 1 | 1 1 2 2 | 2 2 1 1 | 1 2 1 2 | 2 2 2 1 | 2 2 2 2 | 2 Exactly 4 of the ways have the 2nd smallest element equal to 2.
```
3
```
```
1
```
```
3
```
```
2
```
```
2
```
```
Returns: 0.48148148148148145
```
There are 27 ways to choose 3 numbers from the interval 1..3, 13 of them have the 2nd smallest element equal to 2.
```
10
```
```
1
```
```
10
```
```
1
```
```
10
```
```
Returns: 1.0000000000000003E-10
```
Only one of 1010 ways to choose 10 numbers from the interval 1..10 has 1 as the 10th smallest element.
```
4
```
```
61
```
```
65
```
```
62
```
```
3
```
```
Returns: 0.15200000000000002
```

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.