Problem Description

You are given an array of coins where each coin has a specific probability of landing heads when tossed. The i-th coin has a probability prob[i] of showing heads.

Your task is to find the probability that exactly target number of coins will show heads when you toss all the coins exactly once.

For example, if you have 3 coins with probabilities [0.5, 0.5, 0.5] and you want exactly 2 coins to show heads (target = 2), you need to calculate the probability of getting exactly 2 heads when tossing all 3 coins.

The solution uses dynamic programming where f[i][j] represents the probability of getting exactly j heads after tossing the first i coins. The state transition considers two cases for each coin:

• The coin shows tails (probability 1 - p): contributes to f[i][j] from f[i-1][j]
• The coin shows heads (probability p): contributes to f[i][j] from f[i-1][j-1]

The final answer is f[n][target], which gives the probability of getting exactly target heads after tossing all n coins.

Intuition

When we need to find the probability of getting exactly target heads from tossing multiple coins, we need to consider all possible ways this can happen. This naturally leads us to think about building up the solution incrementally - what happens as we add one coin at a time?

Let's think about it step by step. If we've already tossed some coins and know the probability distributions of getting different numbers of heads, how does adding one more coin change things?

When we toss a new coin, two things can happen:

1. It shows tails - the number of heads stays the same
2. It shows heads - the number of heads increases by 1

This observation suggests we can build our solution by tracking probabilities as we process each coin sequentially. For each coin we add, we update our probability distribution based on what happened with the previous coins.

The key insight is that to get exactly j heads after tossing i coins, we could have either:

• Had j heads from the first i-1 coins and the i-th coin showed tails (probability 1 - prob[i])
• Had j-1 heads from the first i-1 coins and the i-th coin showed heads (probability prob[i])

This recursive relationship naturally leads to a dynamic programming approach where we build a table f[i][j] representing the probability of getting exactly j heads from the first i coins. We start with the base case f[0][0] = 1 (probability of getting 0 heads with 0 coins is 1) and build up our solution coin by coin until we reach f[n][target].

Learn more about Math and Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D table. Let's define f[i][j] as the probability of getting exactly j heads after tossing the first i coins.

Initialization:

• Create a 2D array f with dimensions (n+1) × (target+1) where n is the number of coins
• Set f[0][0] = 1 as the base case (probability of 0 heads with 0 coins is 1)
• All other values start at 0

State Transition: For each coin i (from 1 to n) and each possible number of heads j (from 0 to min(i, target)):

where p is prob[i-1] (the probability of the i-th coin showing heads).

Implementation Details:

1. We iterate through each coin using enumerate(prob, 1) to get both the probability p and the 1-indexed position i
2. For each coin, we only need to consider up to min(i, target) heads since:
   • We can't have more heads than coins tossed (hence i)
   • We don't need to track more than target heads
3. For each state f[i][j]:
   • We always add the contribution from the coin showing tails: (1 - p) * f[i-1][j]
   • If j > 0, we also add the contribution from the coin showing heads: p * f[i-1][j-1]

Space Optimization Note: While the solution uses a 2D array, it can be optimized to use only 1D space since each state f[i][j] only depends on the previous row f[i-1]. However, the provided solution uses the 2D approach for clarity.

The final answer is f[n][target], which gives the probability of getting exactly target heads after tossing all n coins.

Example Walkthrough

Let's walk through a small example with 3 coins having probabilities [0.4, 0.6, 0.5] and we want exactly target = 2 heads.

We'll build a DP table f[i][j] where i represents coins processed (0 to 3) and j represents number of heads (0 to 2).

Initial State:

f[0][0] = 1.0  (0 coins, 0 heads: certain)
f[0][1] = 0    (0 coins, 1 head: impossible)
f[0][2] = 0    (0 coins, 2 heads: impossible)

Processing Coin 1 (prob = 0.4):

• f[1][0]: Get 0 heads with 1 coin
  • Coin 1 shows tails: (1 - 0.4) × f[0][0] = 0.6 × 1.0 = 0.6
• f[1][1]: Get 1 head with 1 coin
  • Coin 1 shows tails: (1 - 0.4) × f[0][1] = 0.6 × 0 = 0
  • Coin 1 shows heads: 0.4 × f[0][0] = 0.4 × 1.0 = 0.4
  • Total: 0 + 0.4 = 0.4

Processing Coin 2 (prob = 0.6):

• f[2][0]: Get 0 heads with 2 coins
  • Coin 2 shows tails: (1 - 0.6) × f[1][0] = 0.4 × 0.6 = 0.24
• f[2][1]: Get 1 head with 2 coins
  • Coin 2 shows tails: (1 - 0.6) × f[1][1] = 0.4 × 0.4 = 0.16
  • Coin 2 shows heads: 0.6 × f[1][0] = 0.6 × 0.6 = 0.36
  • Total: 0.16 + 0.36 = 0.52
• f[2][2]: Get 2 heads with 2 coins
  • Coin 2 shows tails: (1 - 0.6) × f[1][2] = 0.4 × 0 = 0
  • Coin 2 shows heads: 0.6 × f[1][1] = 0.6 × 0.4 = 0.24
  • Total: 0 + 0.24 = 0.24

Processing Coin 3 (prob = 0.5):

• f[3][0]: Get 0 heads with 3 coins
  • Coin 3 shows tails: (1 - 0.5) × f[2][0] = 0.5 × 0.24 = 0.12
• f[3][1]: Get 1 head with 3 coins
  • Coin 3 shows tails: (1 - 0.5) × f[2][1] = 0.5 × 0.52 = 0.26
  • Coin 3 shows heads: 0.5 × f[2][0] = 0.5 × 0.24 = 0.12
  • Total: 0.26 + 0.12 = 0.38
• f[3][2]: Get 2 heads with 3 coins
  • Coin 3 shows tails: (1 - 0.5) × f[2][2] = 0.5 × 0.24 = 0.12
  • Coin 3 shows heads: 0.5 × f[2][1] = 0.5 × 0.52 = 0.26
  • Total: 0.12 + 0.26 = 0.38

Final Answer: f[3][2] = 0.38

The probability of getting exactly 2 heads when tossing all 3 coins is 0.38 or 38%.

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n × target), where n is the number of coins (length of the prob array). This is because we have two nested loops: the outer loop iterates through all n coins, and the inner loop iterates up to min(i, target) + 1 times, which in the worst case is target + 1 times. Each operation inside the nested loops takes constant time.

The space complexity as implemented in the code is O(n × (target + 1)) or simply O(n × target), since we create a 2D array f with dimensions (n + 1) × (target + 1). However, the reference answer mentions O(target) space complexity, which would be achievable through space optimization. Since we only need the previous row f[i-1] to compute the current row f[i], we could optimize the space by using only two 1D arrays of size target + 1 (or even just one array with careful updating from right to left), reducing the space complexity to O(target).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating Point Precision Errors

When dealing with probability calculations involving multiple multiplications of decimal values, floating-point precision errors can accumulate, especially when the number of coins is large or probabilities are very small.

Problem Example:

# With many coins, small probabilities compound
prob = [0.0001] * 100
target = 50
# The result might have significant precision errors

Solution:

• Use Python's decimal module for higher precision when needed
• Consider working with log probabilities for very small values
• Round the final result to a reasonable number of decimal places

from decimal import Decimal, getcontext

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        # Set higher precision if needed
        getcontext().prec = 50
      
        num_coins = len(prob)
        prob_decimal = [Decimal(str(p)) for p in prob]
      
        dp = [[Decimal(0)] * (target + 1) for _ in range(num_coins + 1)]
        dp[0][0] = Decimal(1)
      
        for i in range(1, num_coins + 1):
            current_coin_prob = prob_decimal[i - 1]
            for j in range(min(i, target) + 1):
                dp[i][j] = (Decimal(1) - current_coin_prob) * dp[i - 1][j]
                if j > 0:
                    dp[i][j] += current_coin_prob * dp[i - 1][j - 1]
      
        return float(dp[num_coins][target])

2. Memory Inefficiency with Large Inputs

The 2D DP table uses O(n × target) space, which can be excessive when both values are large.

Problem Example:

prob = [0.5] * 10000
target = 5000
# This creates a 10001 × 5001 matrix, using excessive memory

Solution: Use space-optimized DP with rolling arrays since we only need the previous row:

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        num_coins = len(prob)
      
        # Use only two rows instead of full 2D array
        prev = [0.0] * (target + 1)
        curr = [0.0] * (target + 1)
        prev[0] = 1.0
      
        for i in range(1, num_coins + 1):
            current_coin_prob = prob[i - 1]
          
            for j in range(min(i, target) + 1):
                curr[j] = (1 - current_coin_prob) * prev[j]
                if j > 0:
                    curr[j] += current_coin_prob * prev[j - 1]
          
            # Swap arrays for next iteration
            prev, curr = curr, prev
      
        return prev[target]

3. Incorrect Loop Boundaries

A common mistake is setting incorrect upper bounds for the inner loop, either processing unnecessary states or missing valid ones.

Problem Example:

# Incorrect: Processing j up to target even when i < target
for j in range(target + 1):  # Wrong!
    dp[i][j] = ...
# This attempts to calculate impossible states like 5 heads with 2 coins

Solution: Always use min(i, target) as the upper bound:

for j in range(min(i, target) + 1):  # Correct
    # Process only valid states

4. Edge Case: Target Greater Than Number of Coins

If target > len(prob), it's impossible to get more heads than coins available.

Problem Example:

prob = [0.5, 0.5]
target = 3  # Impossible to get 3 heads with 2 coins

Solution: Add an early return check:

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        num_coins = len(prob)
      
        # Early return for impossible cases
        if target > num_coins:
            return 0.0
      
        # Rest of the implementation...