We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Toss Strange Coins

Number: 1166

Difficulty: Medium

Paid? Yes

Companies: Twitch

Problem Description

You are given an array of coin probabilities where the i-th coin lands heads with probability prob[i]. Toss all coins exactly once and return the probability that exactly target coins show heads.

Key Insights

  • Each coin toss is an independent event.
  • Use dynamic programming (DP) to calculate the probability of obtaining a specific number of heads.
  • For each coin, update the DP array in reverse order to avoid overwriting earlier computed probabilities.
  • The recurrence relation is: dp[j] = dp[j-1] * prob[i] + dp[j] * (1 - prob[i]).

Space and Time Complexity

Time Complexity: O(n * target), where n is the number of coins.
Space Complexity: O(target), using a one-dimensional DP array.

Solution

We employ a dynamic programming approach where dp[j] represents the probability of getting exactly j heads at the current stage. We initialize dp[0] to 1 (base case: zero coins tossed yields 0 heads with probability 1), and then for each coin, update the dp array by iterating from target down to 0. This avoids interference from the current coin’s updates affecting future calculations within the same iteration. The final answer is dp[target] after processing all coins.

Code Solutions

# Python solution for Toss Strange Coins

def probabilityOfHeads(prob, target):
    # Initialize a DP array with target+1 elements set to 0
    dp = [0.0] * (target + 1)
    dp[0] = 1.0  # Base case: 0 heads with probability 1
    
    # Loop over each coin's probability
    for p in prob:
        # Update dp array in reverse to avoid using updated values in this iteration
        for j in range(min(target, len(dp)-1), -1, -1):
            # If j is 0, only update for tails using current probability
            if j == 0:
                dp[j] = dp[j] * (1 - p)
            else:
                # dp[j] is updated by considering both the current coin being head and tail
                dp[j] = dp[j-1] * p + dp[j] * (1 - p)
    return dp[target]

# Example usage:
print(probabilityOfHeads([0.4], 1))  # Expected output: 0.4
print(probabilityOfHeads([0.5, 0.5, 0.5, 0.5, 0.5], 0))  # Expected output: 0.03125
← Back to All Questions