Toss Strange Coins - Solution & Explanation
Problem Statement
You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.
Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.
Example 1:
Input: prob = [0.4], target = 1 Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125
Constraints:
1 <= prob.length <= 10000 <= prob[i] <= 10 <= target<= prob.length- Answers will be accepted as correct if they are within
10^-5of the correct answer.
Approach Overview
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.
Approach 1: Dynamic Programming
Let f[i][j] represent the probability of having j coins facing up in the first i coins, and initially f[0][0]=1. The answer is f[n][target].
Consider f[i][j], where i geq 1. If the current coin is facing down, then f[i][j] = (1 - p) times f[i - 1][j]; If the current coin is facing up and j \gt 0, then f[i][j] = p times f[i - 1][j - 1]. Therefore, the state transition equation is:
$
f[i][j] = \begin{cases}
(1 - p) times f[i - 1][j], & j = 0 \
(1 - p) times f[i - 1][j] + p times f[i - 1][j - 1], & j \gt 0
\end{cases}
where p represents the probability of the i-th coin facing up.
We note that the state f[i][j] is only related to f[i - 1][j] and f[i - 1][j - 1], so we can optimize the two-dimensional space into one-dimensional space.
The time complexity is O(n times target), and the space complexity is O(target). Where n$ is the number of coins.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| 2D Dynamic Programming | O(n × target) | O(n × target) | Best for understanding the DP state and transitions clearly |
| Space-Optimized Dynamic Programming | O(n × target) | O(target) | Preferred in interviews and production when memory usage matters |
Video Solution
1230 Toss Strange Coins • Kelvin Chandra • 1,449 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Toss Strange Coins easy or hard?
Toss Strange Coins Python/Java solution
What is the best approach for Toss Strange Coins?
How to solve Toss Strange Coins in O(n × target)?
Is Toss Strange Coins asked at Google/Amazon/Meta?
What data structure is used in Toss Strange Coins?
What is the time complexity of Toss Strange Coins?
Ready to solve this problem?
Practice Toss Strange Coins with our built-in code editor and test cases.
Practice on FleetCode