Toss Strange Coins - Solution & Explanation

Problem Overview: You are given an array where prob[i] represents the probability that the i-th coin lands heads. After tossing all coins once, compute the probability of getting exactly target heads. Each coin is independent, so the result depends on combining probabilities across multiple toss outcomes.

Approach 1: 2D Dynamic Programming (O(n × target) time, O(n × target) space)

This approach models the problem using a DP table where dp[i][j] stores the probability of getting exactly j heads after tossing the first i coins. For each coin, two outcomes are possible: heads or tails. If the coin lands heads, you transition from dp[i-1][j-1]; if it lands tails, you transition from dp[i-1][j]. The transition becomes dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1 - prob[i-1]). Iterate through all coins and possible head counts up to target. This solution is straightforward and clearly expresses the state transition typical in dynamic programming problems involving cumulative probabilities.

Approach 2: Space-Optimized Dynamic Programming (O(n × target) time, O(target) space)

The previous DP only depends on the previous row, so you can compress the table into a single array of size target + 1. Iterate through coins and update probabilities in reverse order to avoid overwriting states that are still needed. For each coin probability p, update dp[j] = dp[j] * (1 - p) + dp[j-1] * p for j from target down to 1. Also update dp[0] *= (1 - p) since getting zero heads requires every processed coin to land tails. This version keeps the same logic but reduces memory usage significantly. The technique appears frequently in array-based DP optimizations and probability transitions.

Both approaches rely on the same mathematical insight: each coin contributes two weighted outcomes that propagate through the DP states. The recurrence essentially builds a probability distribution over the number of heads after each toss, a common pattern in probability DP problems.

Recommended for interviews: The space-optimized dynamic programming approach. Interviewers expect you to recognize the probability transition and reduce the DP table to a 1D array. Showing the full 2D formulation first demonstrates understanding of the state definition, while the optimized version shows strong DP optimization skills.