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 <= 10000 <= prob[i] <= 10 <= target <= prob.length- Answers will be accepted as correct if they are within
10^-5 of the correct answer.
Solutions
Solution 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 ≥ 1. If the current coin is facing down, then f[i][j] = (1 - p) × f[i - 1][j]; If the current coin is facing up and j \gt 0, then f[i][j] = p × f[i - 1][j - 1]. Therefore, the state transition equation is:
f[i][j] = \begin{cases}
(1 - p) × f[i - 1][j], & j = 0 \
(1 - p) × f[i - 1][j] + p × 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 × target), and the space complexity is O(target). Where n is the number of coins.
PythonJavaC++GoTypeScript
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
n = len(prob)
f = [[0] * (target + 1) for _ in range(n + 1)]
f[0][0] = 1
for i, p in enumerate(prob, 1):
for j in range(min(i, target) + 1):
f[i][j] = (1 - p) * f[i - 1][j]
if j:
f[i][j] += p * f[i - 1][j - 1]
return f[n][target](code-box)
class Solution {
public double probabilityOfHeads(double[] prob, int target) {
int n = prob.length;
double[][] f = new double[n + 1][target + 1];
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= Math.min(i, target); ++j) {
f[i][j] = (1 - prob[i - 1]) * f[i - 1][j];
if (j > 0) {
f[i][j] += prob[i - 1] * f[i - 1][j - 1];
}
}
}
return f[n][target];
}
}(code-box)
class Solution {
public:
double probabilityOfHeads(vector<double>& prob, int target) {
int n = prob.size();
double f[n + 1][target + 1];
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= min(i, target); ++j) {
f[i][j] = (1 - prob[i - 1]) * f[i - 1][j];
if (j > 0) {
f[i][j] += prob[i - 1] * f[i - 1][j - 1];
}
}
}
return f[n][target];
}
};(code-box)
func probabilityOfHeads(prob []float64, target int) float64 {
n := len(prob)
f := make([][]float64, n+1)
for i := range f {
f[i] = make([]float64, target+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 0; j <= i && j <= target; j++ {
f[i][j] = (1 - prob[i-1]) * f[i-1][j]
if j > 0 {
f[i][j] += prob[i-1] * f[i-1][j-1]
}
}
}
return f[n][target]
}(code-box)
function probabilityOfHeads(prob: number[], target: number): number {
const n = prob.length;
const f = new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j <= target; ++j) {
f[i][j] = f[i - 1][j] * (1 - prob[i - 1]);
if (j) {
f[i][j] += f[i - 1][j - 1] * prob[i - 1];
}
}
}
return f[n][target];
}(code-box)
Solution 2
PythonJavaC++GoTypeScript
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
f = [0] * (target + 1)
f[0] = 1
for p in prob:
for j in range(target, -1, -1):
f[j] *= 1 - p
if j:
f[j] += p * f[j - 1]
return f[target](code-box)
class Solution {
public double probabilityOfHeads(double[] prob, int target) {
double[] f = new double[target + 1];
f[0] = 1;
for (double p : prob) {
for (int j = target; j >= 0; --j) {
f[j] *= (1 - p);
if (j > 0) {
f[j] += p * f[j - 1];
}
}
}
return f[target];
}
}(code-box)
class Solution {
public:
double probabilityOfHeads(vector<double>& prob, int target) {
double f[target + 1];
memset(f, 0, sizeof(f));
f[0] = 1;
for (double p : prob) {
for (int j = target; j >= 0; --j) {
f[j] *= (1 - p);
if (j > 0) {
f[j] += p * f[j - 1];
}
}
}
return f[target];
}
};(code-box)
func probabilityOfHeads(prob []float64, target int) float64 {
f := make([]float64, target+1)
f[0] = 1
for _, p := range prob {
for j := target; j >= 0; j-- {
f[j] *= (1 - p)
if j > 0 {
f[j] += p * f[j-1]
}
}
}
return f[target]
}(code-box)
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];
}(code-box)
