876. Biased Coin Tosses
A game stall owns n unfair coins, tossed once each and independently. Coin i lands heads with probability prob[i] and tails with probability 1 - prob[i]. A visitor wins a prize when the number of heads across all coins is exactly target.
Return the probability that the visitor wins. An answer within 1e-6 of the true value is accepted. Probabilities may be exactly 0 or 1, and target can be 0. Each coin is independent of all the others, so the order of the coins does not matter.
Example 1
- Input:
- prob = [0.5,0.5], target = 1
- Output:
- 0.5
- Explanation:
Two fair coins: exactly one head happens with probability 0.5 (HT or TH).
Example 2
- Input:
- prob = [0.1,0.8,0.5], target = 2
- Output:
- 0.41000000000000003
- Explanation:
Exactly two heads: the three ways add to 0.1*0.8*0.5 + 0.1*0.2*0.5 + 0.9*0.8*0.5 = 0.04 + 0.01 + 0.36 = 0.41.
Example 3
- Input:
- prob = [0.3], target = 0
- Output:
- 0.7
- Explanation:
The single coin must land tails: probability 0.7.
Constraints
- 1 ≤ prob.length ≤ 5000
- 0 ≤ prob[i] ≤ 1
- 0 ≤ target ≤ min(prob.length, 100)
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n * target)
- Space
- O(target)