Problem Description

You are given a list of probabilities prob, where prob[i] is the probability of the ith coin landing on heads. You have n such coins, and you want to toss all of them. Given an integer target, your goal is to determine the probability that exactly target coins will show heads after all coins are tossed.

• Each coin is tossed exactly once.
• prob[i] is a floating-point number in the range [0, 1].
• Return the probability as a floating-point number.
• Constraints: 1 <= n <= 1000, and 0 <= target <= n.

Thought Process

At first glance, you might think to try all possible ways the coins can land and count the ones with exactly target heads. However, with up to 1000 coins, there are 2¹⁰⁰⁰ possible outcomes, so brute-force enumeration is computationally impossible.

Instead, notice that this is a variation of the classic "coin toss" problem, but each coin has its own probability of heads. This suggests using dynamic programming to build up the answer efficiently, by calculating the probability of getting a certain number of heads after tossing each coin.

By thinking recursively, we can express the probability of getting k heads after tossing the first i coins in terms of the probabilities after tossing i-1 coins. This allows us to avoid recomputation and solve the problem efficiently.

Solution Approach

We use dynamic programming to solve the problem. The idea is to maintain an array dp where dp[k] represents the probability of getting exactly k heads after tossing some coins.

1. Initialization:
   • Before tossing any coins, the probability of having 0 heads is 1 (dp[0] = 1.0), and all others are 0.
2. Iterate through each coin:
   • For each coin, update the dp array from high to low (to avoid overwriting needed values).
   • For each possible number of heads k (from current coin count down to 0):
   • If the current coin is heads, increase the head count by 1, so dp[k] += dp[k-1] * prob[i].
   • If the current coin is tails, dp[k] *= (1 - prob[i]).
3. Final Answer:
   • After processing all coins, dp[target] holds the required probability.

This approach ensures we only use O(n) space and O(n²) time, which is efficient for the given constraints.

Example Walkthrough

Suppose prob = [0.5, 0.5, 0.5] and target = 2.

1. Initialization: dp = [1.0, 0.0, 0.0, 0.0]
2. First coin (0.5):
   • For 1 head: dp[1] += dp[0] * 0.5 = 1.0 * 0.5 = 0.5
   • For 0 heads: dp[0] *= 0.5 = 1.0 * 0.5 = 0.5
   • Now: dp = [0.5, 0.5, 0.0, 0.0]
3. Second coin (0.5):
   • For 2 heads: dp[2] += dp[1] * 0.5 = 0.5 * 0.5 = 0.25
   • For 1 head: dp[1] = dp[1] * 0.5 + dp[0] * 0.5 = 0.5*0.5 + 0.5*0.5 = 0.5
   • For 0 heads: dp[0] *= 0.5 = 0.5 * 0.5 = 0.25
   • Now: dp = [0.25, 0.5, 0.25, 0.0]
4. Third coin (0.5):
   • For 3 heads: dp[3] += dp[2] * 0.5 = 0.25 * 0.5 = 0.125
   • For 2 heads: dp[2] = dp[2] * 0.5 + dp[1] * 0.5 = 0.25*0.5 + 0.5*0.5 = 0.125 + 0.25 = 0.375
   • For 1 head: dp[1] = dp[1] * 0.5 + dp[0] * 0.5 = 0.5*0.5 + 0.25*0.5 = 0.25 + 0.125 = 0.375
   • For 0 heads: dp[0] *= 0.5 = 0.25 * 0.5 = 0.125
   • Now: dp = [0.125, 0.375, 0.375, 0.125]
5. Final answer: dp[2] = 0.375

So, the probability of getting exactly 2 heads is 0.375.

Time and Space Complexity

• Brute-force approach:
  • Time: O(2ⁿ), since all possible outcomes are checked.
  • Space: O(1), unless storing all outcomes.
• Dynamic programming approach:
  • Time: O(n²), because for each coin, we update up to n entries in the dp array.
  • Space: O(n), since we only need to keep the current state of the dp array.

Summary

The "Toss Strange Coins" problem is a classic example of dynamic programming applied to probability. By carefully updating an array that tracks the probability of each possible number of heads, we efficiently compute the answer without brute-forcing every outcome. The elegance lies in reusing subproblem solutions and leveraging the independence of each coin toss.

Code Implementation

class Solution:
    def probabilityOfHeads(self, prob, target):
        n = len(prob)
        dp = [0.0] * (target + 1)
        dp[0] = 1.0
        for i in range(n):
            p = prob[i]
            for k in range(min(target, i + 1), 0, -1):
                dp[k] = dp[k] * (1 - p) + dp[k - 1] * p
            dp[0] = dp[0] * (1 - p)
        return dp[target]
      

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int n = prob.size();
        vector<double> dp(target + 1, 0.0);
        dp[0] = 1.0;
        for (int i = 0; i < n; ++i) {
            double p = prob[i];
            for (int k = min(target, i + 1); k >= 1; --k) {
                dp[k] = dp[k] * (1 - p) + dp[k - 1] * p;
            }
            dp[0] = dp[0] * (1 - p);
        }
        return dp[target];
    }
};
      

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) {
            double p = prob[i];
            for (int k = Math.min(target, i + 1); k >= 1; --k) {
                dp[k] = dp[k] * (1 - p) + dp[k - 1] * p;
            }
            dp[0] = dp[0] * (1 - p);
        }
        return dp[target];
    }
}
      

var probabilityOfHeads = function(prob, target) {
    let n = prob.length;
    let dp = new Array(target + 1).fill(0.0);
    dp[0] = 1.0;
    for (let i = 0; i < n; ++i) {
        let p = prob[i];
        for (let k = Math.min(target, i + 1); k >= 1; --k) {
            dp[k] = dp[k] * (1 - p) + dp[k - 1] * p;
        }
        dp[0] = dp[0] * (1 - p);
    }
    return dp[target];
};