Domain 2MediumMEDIUM

Toss Strange Coins

Calculate the probability of getting exactly target heads using a space-optimized DP approach similar to the knapsack problem.

Domain: medium•Updated: 2026-09-10
#Dynamic Programming#Array/List#$O(N cdot K)$#$O(K)

Problem Breakdown

We are given an array prob where each element represents the independent probability that coin ii lands on heads. We need to determine the total probability of obtaining exactly target heads after tossing all coins once.

Inputs:

  • prob: A list of floats (0≤prob[i]≤10 \le prob[i] \le 1).
  • target: An integer representing the exact number of heads required (0≤target≤len(prob)0 \le target \le len(prob)).

Outputs:

  • A single float value representing the calculated probability. The result must be accurate within 10−510^{-5} tolerance.

Key Constraints & Considerations:

  • Independence: Coin tosses are independent events, meaning probabilities multiply along specific paths (sequences of outcomes).
  • Precision: Floating-point arithmetic is used; standard double precision (float in Python) handles the required accuracy for N=1000N=1000.
  • State Space: We need to track how many heads we have accumulated so far.

Intuition

A brute-force approach would iterate through all combinations of coins that result in target heads, which is exponential (O(2N)O(2^N)). This will time out for N=1000N=1000.

Key Insight: This problem can be modeled using Dynamic Programming (DP), specifically resembling the 0/1 Knapsack Problem structure. Instead of maximizing value or counting ways with integers, we are summing probabilities.

  • Let dp[j] represent the probability of obtaining exactly j heads after processing a subset of coins.
  • When considering a new coin with head-probability pp:
    • Tails (prob 1−p1-p): The number of heads remains unchanged (j→jj \to j). We multiply existing probabilities by (1−p)(1-p).
    • Heads (prob pp): The count increases by one. We transition from state dp[j-1] to dp[j].

State Transition: To calculate the new probability for having exactly j heads after including a coin, we consider two mutually exclusive scenarios:

  1. The current coin is Tails (prob 1−p1-p): Probability comes from previously having j heads (dpold[j]dp_{old}[j]). Contribution: dp[j]×(1−p)dp[j] \times (1-p).
  2. The current coin is Heads (prob pp): Probability comes from previously having j-1 heads (dpold[j−1]dp_{old}[j-1]). Contribution: dp[j−1]×pdp[j-1] \times p.

Optimization: To save space, we use a single 1D array for the DP table. We must iterate backwards (from target down to 0) when updating this array so that when calculating dp[j], the value of dp[j-1] used corresponds to the state before processing the current coin.

Approach

  1. Initialization: Create a DP array dp of size target + 1. Initialize all values to 0.0. Set dp[0] = 1.0, representing that with 0 coins processed, there is probability 1 of having exactly 0 heads (base case).
  2. Iteration: Loop through each coin’s probability in the input list.
  3. Update Logic: For each coin, iterate backwards from target down to 0. Update dp[j] using the transition formula derived above: new_prob=dpold[j]∗(1−p)+dpold[j−1]∗pnew\_prob = dp_{old}[j]*(1-p) + dp_{old}[j-1]*p. Handle index 0 separately as it only has one valid path (must be Tails).
  4. Result: After processing all coins, return dp[target].

Complexity Analysis

  • Time Complexity: O(N⋅target)O(N \cdot target) where NN is the number of coins and target is the desired head count. In each iteration over NN, we update up to target states. Given constraints (N=1000,target≤1000N=1000, target \le 1000), operations are roughly 12N2≈5×105\frac{1}{2} N^2 \approx 5 \times 10^5, which is well within time limits for Python (typically allowing ~ 107−10810^7-10^8 ops/sec).
  • Space Complexity: O(target)O(target). We use a single array of size target + 1. This reduces space from the naive 2D2D table (N⋅targetN \cdot target) to linear with respect to the output dimension.

Solution

def strangeCoins(prob: list[float], target: int) -> float:
    # Initialize DP array where dp[j] stores probability of getting exactly j heads
    n = len(prob)
    
    # Defensive check for empty input, though constraints guarantee N >= 1
    if not prob or target < 0: 
        return 0.0
        
    # Base case: Probability of having 0 heads with 0 coins processed is 1.0
    dp = [0.0] * (target + 1)
    dp[0] = 1.0
    
    for p in prob:
        # Iterate backwards to update DP table using values from the previous iteration only
        # This prevents double-counting the current coin's contribution within the same step
        for j in range(target, -1, -1):
            if j == 0:
                # If we want exactly 0 heads, this coin must be Tails. 
                # We multiply existing probability of 0 heads by (1-p).
                dp[0] *= (1.0 - p)
            else:
                # Transition logic for j > 0:
                # Either current coin was Head (add to count from j-1 state) OR
                # Current coin was Tail (keep same count, multiply existing prob by tail probability).
                dp[j] = dp[j] * (1.0 - p) + dp[j-1] * p
                
    return dp[target]

Edge Cases Handled

  • Target 0: The code correctly initializes dp[0]=1 and multiplies by (1-p) for every coin, resulting in the probability that all coins are tails.
  • Probabilities of 0 or 1: If a coin has p=1p=1, it forces heads (term with (1−p)(1-p) becomes 0). If p=0p=0, it forces tails (term with dp[j-1]*p becomes 0). The math holds without special checks.
  • Target > Possible Heads: Since we initialize the array to size target + 1, indices beyond what is physically possible given processed coins will remain 0 until enough heads are accumulated, naturally handling cases where exact target count isn’t reachable yet (though with probability logic, it’s always mathematically valid).
  • Empty Input: While constraints say N≥1N \ge 1, the check if not prob ensures safety against unexpected empty lists.