Toss Strange Coins - Leetcode Solution

Problem Statement:

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:

Input: prob = [0.4], target = 1 Output: 0.4

Input: prob = [0.2,0.8,0.4], target = 1 Output: 0.4800000000000001

Solution:

As given, we have ‘n’ coins and each coin has a probability ‘p’ of tossing heads. The problem requires us to find the probability of getting exactly ‘k’ number of coins facing heads.

To solve this problem, we will be using Dynamic Programming (DP). We will be using a 2-D DP approach here.

The DP equation is given below:

dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i]);

The first dimension ‘i’ will represent the number of coins we have considered so far and the second dimension ‘j’ will represent the number of heads we have observed so far. In other words, dp[i][j] denotes probability of getting exactly ‘j’ heads while tossing first ‘i’ coins.

The base case for DP is dp[0][0] where the probability of getting 0 heads while tossing 0 coins is 1.

Python Code:

def probabilityOfHeads(prob, target): n = len(prob) dp = [[0]*(target+1) for _ in range(n+1)] dp[0][0] = 1

for i in range(1,n+1):
    for j in range(target+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1-prob[i-1])
        else:
            dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1 - prob[i-1])

return dp[n][target]

1