Toss Strange Coins

medium dynamic programming probability math

Problem

You have a list of biased coins, where prob[i] is the probability that the i-th coin lands heads when tossed. Toss every coin exactly once and return the probability that the number of coins showing heads equals target.

Inputprob = [0.5, 0.5, 0.5], target = 2

Output0.375

There are C(3, 2) = 3 ways to pick which two coins are heads, each with probability 0.5³ = 0.125, so 3 × 0.125 = 0.375.

prob (comma-separated, each in [0,1])

target

def toss_strange_coins(prob, target):
    dp = [0.0] * (target + 1)
    dp[0] = 1.0
    for p in prob:
        for j in range(target, -1, -1):
            dp[j] = dp[j] * (1 - p) + (dp[j - 1] * p if j > 0 else 0.0)
    return dp[target]

function tossStrangeCoins(prob, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (const p of prob) {
    for (let j = target; j >= 0; j--) {
      dp[j] = dp[j] * (1 - p) + (j > 0 ? dp[j - 1] * p : 0);
    }
  }
  return dp[target];
}

class Solution {
    public double tossStrangeCoins(double[] prob, int target) {
        double[] dp = new double[target + 1];
        dp[0] = 1.0;
        for (double p : prob) {
            for (int j = target; j >= 0; j--) {
                dp[j] = dp[j] * (1 - p) + (j > 0 ? dp[j - 1] * p : 0.0);
            }
        }
        return dp[target];
    }
}

double tossStrangeCoins(vector<double>& prob, int target) {
    vector<double> dp(target + 1, 0.0);
    dp[0] = 1.0;
    for (double p : prob) {
        for (int j = target; j >= 0; j--) {
            dp[j] = dp[j] * (1 - p) + (j > 0 ? dp[j - 1] * p : 0.0);
        }
    }
    return dp[target];
}

Explanation

We want the probability of getting exactly target heads. The key idea is to toss the coins one at a time and keep a running table dp, where dp[k] is the probability of having exactly k heads so far.

We start with dp[0] = 1: before tossing anything, we are guaranteed zero heads. Then for each coin with heads-probability p, every count k updates using two cases — the coin lands tails (count stays at k) or heads (count came from k-1).

That gives the formula dp[j] = dp[j]·(1-p) + dp[j-1]·p. We sweep j from target down to 0 so that dp[j-1] still holds the value from before this coin was tossed, not after.

Example: prob = [0.5, 0.5, 0.5], target = 2. After all three fair coins, the chance of exactly 2 heads is the 3 ways to choose them times 0.5³, which is 3 × 0.125 = 0.375 — exactly dp[2].

Because we only ever keep target + 1 probabilities and update them in place, this is fast and uses very little memory.

Time: O(n · target) Space: O(target)