#1230
Medium Algorithms Toss strange coins
Array Math Dynamic Programming Probability and Statistics
58.1% acceptance
Mar 31, 2026
409
53
No description available.
Solution
Rust
Time O(n²)
Space O(n)
impl Solution {
pub fn probability_of_heads(prob: Vec<f64>, target: i32) -> f64 {
let n = prob.len();
let t = target as usize;
// dp[j] = probability of getting exactly j heads
let mut dp = vec![0.0; t + 1];
dp[0] = 1.0 - prob[0];
if t > 0 { /* do nothing, will set below */ }
// Reset: dp[0] = prob of 0 heads after first coin
dp[0] = 1.0 - prob[0];
if t >= 1 {
dp[1] = prob[0];
}
for i in 1..n {
// iterate backwards to avoid overwriting
let limit = t.min(i + 1);
for j in (0..=limit).rev() {
dp[j] = dp[j] * (1.0 - prob[i]) + if j > 0 { dp[j - 1] * prob[i] } else { 0.0 };
}
}
dp[t]
}
}