1230

1230. Toss Strange Coins (Medium)

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 <= 1000
• 0 <= prob[i] <= 1
• 0 <= target <= prob.length
• Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Companies:
Google

Related Topics:
Math, Dynamic Programming, Probability and Statistics

Solution 1. DP

The brute force idea is DFS, or better, DFS + Memo -- for each coin, try head or tail. The time complexity is O(C(N, T)) where C(N, T) is the number of combinations picking T elements from total N elements. Since N=1000 at most, in the worst case, C(N, T) is C(1000, 500) which is a very large number.

The second idea is to consider the coins one by one and use Math and DP.

Consider the first 2 coins, assume we have the following distribution

of Heads | Probability

---|--- 2 | a 1 | b 0 | c

Now consider the 3rd coin with head probability x. We'll have a new distribution

of Heads | Probability

---|--- 3|ax 2|bx + a(1-x) 1|cx + b(1-x) 0| c(1-x)

We can see that for each new coin A[i], we just need to go through previous i+1 distributions. This results in a time complexity of O(N^2).

// OJ: https://leetcode.com/problems/toss-strange-coins/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    double probabilityOfHeads(vector<double>& A, int target) {
        double dp[1001] = {[0] = 1}, tmp[1001] = {};
        int N = A.size();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= i + 1; ++j) tmp[j] = 0;
            for (int j = 0; j <= i; ++j) tmp[j + 1] += dp[j] * A[i];
            for (int j = 0; j <= i; ++j) tmp[j] += dp[j] * (1 - A[i]);
            swap(tmp, dp);
        }
        return dp[target];
    }
};

Or

// OJ: https://leetcode.com/problems/toss-strange-coins/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    double probabilityOfHeads(vector<double>& A, int target) {
        int N = A.size();
        vector<double> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i < N; ++i) {
            for (int j = min(i + 1, target); j >= 0; --j) {
                dp[j] = (j ? dp[j - 1] * A[i] : 0) + dp[j] * (1 - A[i]);
            }
        }
        return dp[target];
    }
};