Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1230.html

1230. Toss Strange Coins

Level

Medium

Description

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.

Solution

Use dynamic programming. Let length be the length of array prob, and it can be seen that length equals the number of coins.

Create a 2D array dp with length + 1 rows and target + 1 columns. The element at dp[i][j] stands for the probability that after the first i coins are tossed, there are j coins facing heads.

Obviously, if no coin is tossed, then definitely no coin faces heads, which has a probability 1, so dp[0][0] = 1. Each time a coin is tossed, the number of coins facing heads either remains the same or increase by 1, depending on the current coin’s probability of facing heads. So the probability can be calculated. For the case j equals 0, dp[i][0] only depends on prob[i - 1] and dp[i - 1][0]. For other cases, dp[i][j] depends on prob[i - 1], dp[i - 1][j - 1] and dp[i - 1][j].

Finally, return dp[length][target] for the result.

  • class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        int length = prob.length;
        double[][] dp = new double[length + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= length; i++) {
            double curProb = prob[i - 1];
            dp[i][0] = dp[i - 1][0] * (1 - curProb);
            for (int j = 1; j <= target; j++)
                dp[i][j] = dp[i - 1][j - 1] * curProb + dp[i - 1][j] * (1 - curProb);
        }
        return dp[length][target];
    }
}

  • // OJ: https://leetcode.com/problems/toss-strange-coins/
// 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];
    }
};

  • class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        dp = [0] * (target + 1)
        dp[0] = 1
        for v in prob:
            for j in range(target, -1, -1):
                dp[j] *= 1 - v
                if j >= 1:
                    dp[j] += dp[j - 1] * v
        return dp[-1]



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

  • function probabilityOfHeads(prob: number[], target: number): number {
    const f = new Array(target + 1).fill(0);
    f[0] = 1;
    for (const p of prob) {
        for (let j = target; j >= 0; --j) {
            f[j] *= 1 - p;
            if (j > 0) {
                f[j] += f[j - 1] * p;
            }
        }
    }
    return f[target];
}

All Problems

All Solutions