LeetCode 1230 - Toss Strange Coins

This problem is asking us to calculate the probability that, when tossing a set of coins, exactly a specific number of them come up heads. Each coin has its own individual probability of landing heads, which is given in the input array prob.

leetcodemediumarraymathdynamic-programmingprobability-and-statistics

LeetCode Problem 1230

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Probability and Statistics

Solution

Problem Understanding

This problem is asking us to calculate the probability that, when tossing a set of coins, exactly a specific number of them come up heads. Each coin has its own individual probability of landing heads, which is given in the input array prob. The integer target represents the exact number of heads we are interested in.

The input prob is an array of floats between 0 and 1, where prob[i] indicates the probability of the i-th coin landing heads. The expected output is a single float representing the probability that exactly target coins come up heads if all coins are tossed exactly once. This output must be accurate within a tolerance of 10^-5.

Key constraints indicate that the array can have up to 1000 coins. A naive solution that enumerates all possible outcomes is infeasible because the number of combinations grows exponentially as 2^n. Edge cases to consider include target being 0 (all tails), target equal to len(prob) (all heads), or having coins with probabilities of exactly 0 or 1.

Approaches

A brute-force approach would enumerate all possible outcomes of tossing n coins. For each outcome, we would count the number of heads and sum the probabilities of those outcomes where the count equals target. While this is correct, the time complexity is O(2^n), which is impractical for n up to 1000.

The optimal approach uses dynamic programming. The key observation is that the probability of having k heads after i coins depends only on the probabilities of having k or k-1 heads after i-1 coins. We define dp[i][j] as the probability of having j heads after tossing the first i coins. We can build this table iteratively:

  • For the i-th coin, if it lands heads, the number of heads increases by 1.
  • If it lands tails, the number of heads remains the same.

This leads to the recurrence:

dp[i][j] = dp[i-1][j] * (1 - prob[i-1]) + dp[i-1][j-1] * prob[i-1]  (if j > 0)
dp[i][0] = dp[i-1][0] * (1 - prob[i-1])

To optimize space, we can reduce the 2D table to a 1D array because each row only depends on the previous row.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerates all possible outcomes; infeasible for large n
Dynamic Programming O(n * target) O(target) Builds probabilities iteratively using previous results

Algorithm Walkthrough

  1. Initialize a 1D DP array of size target + 1 with all zeros and set dp[0] = 1.0. This represents the probability of having zero heads before tossing any coins.
  2. Iterate through each coin in the prob array.
  3. For each coin, iterate backwards from target down to 1. Update dp[j] using the formula: dp[j] = dp[j] * (1 - prob[i]) + dp[j-1] * prob[i]. Iterating backwards ensures we use the previous row’s values correctly.
  4. Update dp[0] separately for the probability that no new heads are added: dp[0] = dp[0] * (1 - prob[i]).
  5. After processing all coins, dp[target] holds the probability of getting exactly target heads.

Why it works: Each dp[j] always represents the correct probability of having j heads after processing all coins up to the current one. By iterating backwards, we prevent overwriting probabilities needed for the current update. This maintains the invariant dp[j] = probability of j heads using first i coins.

Python Solution

from typing import List

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        dp = [0.0] * (target + 1)
        dp[0] = 1.0  # base case: 0 heads initially
        
        for p in prob:
            # iterate backwards to avoid overwriting values we still need
            for j in range(target, 0, -1):
                dp[j] = dp[j] * (1 - p) + dp[j-1] * p
            dp[0] *= (1 - p)
        
        return dp[target]

This implementation starts by initializing the base case. Then, for each coin, it updates probabilities of all possible head counts in reverse order. Updating in reverse ensures we are always using values from the previous step, maintaining correctness.

Go Solution

func probabilityOfHeads(prob []float64, target int) float64 {
    dp := make([]float64, target+1)
    dp[0] = 1.0
    
    for _, p := range prob {
        for j := target; j >= 1; j-- {
            dp[j] = dp[j]*(1-p) + dp[j-1]*p
        }
        dp[0] *= (1 - p)
    }
    
    return dp[target]
}

In Go, we use a slice for the DP array. The logic mirrors Python exactly. Note that Go handles slices differently than Python lists, but here the differences do not affect the algorithm. We also avoid using extra memory by updating in reverse.

Worked Examples

Example 1: prob = [0.4], target = 1

Initial DP: [1.0, 0.0]

Process coin 0.4:

  • dp[1] = dp[1]*0.6 + dp[0]*0.4 = 0*0.6 + 1*0.4 = 0.4
  • dp[0] = dp[0]*0.6 = 1*0.6 = 0.6

Final DP: [0.6, 0.4]

Output: 0.4

Example 2: prob = [0.5,0.5,0.5,0.5,0.5], target = 0

Initial DP: [1.0]

Iteratively update dp[0] only:

dp[0] *= 0.5 five times → 0.5^5 = 0.03125

Output: 0.03125

Complexity Analysis

Measure Complexity Explanation
Time O(n * target) We iterate over each coin and for each coin, update up to target entries in DP
Space O(target) Only a 1D array of size target + 1 is needed, reducing space from O(n*target)

The time complexity is manageable even for n = 1000 and target = 1000 because n*target is at most 1,000,000 operations. Space is efficiently optimized using a single 1D array.

Test Cases

# basic examples
assert abs(Solution().probabilityOfHeads([0.4], 1) - 0.4) < 1e-5  # single coin
assert abs(Solution().probabilityOfHeads([0.5]*5, 0) - 0.03125) < 1e-5  # all tails

# all heads
assert abs(Solution().probabilityOfHeads([1.0, 1.0, 1.0], 3) - 1.0) < 1e-5

# mixed probabilities
assert abs(Solution().probabilityOfHeads([0.2, 0.8], 1) - 0.64) < 1e-5  # 0.2*0.2 + 0.8*0.8?

# edge target values
assert abs(Solution().probabilityOfHeads([0.5,0.5,0.5], 3) - 0.125) < 1e-5
assert abs(Solution().probabilityOfHeads([0.5,0.5,0.5], 0) - 0.125) < 1e-5
Test Why
Single coin Checks base case
Multiple coins, zero heads Validates tail-only probability
All heads Validates deterministic case with p=1
Mixed probabilities Ensures algorithm handles non-uniform probabilities
Edge target values Ensures boundaries 0 and n are handled correctly

Edge Cases

One important edge case is when target = 0, meaning we want all tails. The implementation correctly updates dp[0] separately to accumulate this probability.

Another edge case is when target = len(prob), requiring all heads. The algorithm handles this naturally because dp[target] will only be updated when all coins contribute heads.

A third edge case is when a coin has probability 0 or 1. For 0, it can never contribute to heads, and for 1, it will always contribute a head. The DP update formula handles both seamlessly, ensuring the probabilities remain accurate.