Problem

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Examples

Example 1:

1
2

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

1
2

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

  • 1 <= prob.length <= 1000
  • 0 <= prob[i] <= 1
  • 0 <= target ``<= prob.length
  • Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Solution

Method 1 – Dynamic Programming

Intuition

Let dp[i][j] be the probability of getting j heads after tossing the first i coins. For each coin, update the probability for each possible number of heads.

Approach

Use a 1D dp array (rolling array) where dp[j] is the probability of getting j heads so far. For each coin, update dp[j] from high to low.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        int n = prob.length;
        double[] dp = new double[target + 1];
        dp[0] = 1.0;
        for (int i = 0; i < n; ++i) {
            for (int j = Math.min(i + 1, target); j >= 0; --j) {
                dp[j] = (j > 0 ? dp[j - 1] * prob[i] : 0) + dp[j] * (1 - prob[i]);
            }
        }
        return dp[target];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from typing import List
class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        n = len(prob)
        dp = [0.0] * (target + 1)
        dp[0] = 1.0
        for i in range(n):
            for j in range(min(i + 1, target), -1, -1):
                dp[j] = (dp[j - 1] * prob[i] if j > 0 else 0) + dp[j] * (1 - prob[i])
        return dp[target]

Complexity

  • ⏰ Time complexity: O(n * t) where n = number of coins, t = target
  • 🧺 Space complexity: O(t)