Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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]
  }
}