Toss Strange Coins - Practice Coding Problems

Toss Strange Coins - Problem

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.

Note: The answer should be accurate to within 10^-5 of the expected answer.

Input & Output

Example 1 — Basic Case

$ Input: prob = [0.4, 0.6], target = 1

› Output: 0.52

💡 Note: Two ways to get exactly 1 head: coin 1 heads + coin 2 tails (0.4 × 0.4 = 0.16) or coin 1 tails + coin 2 heads (0.6 × 0.6 = 0.36). Total: 0.16 + 0.36 = 0.52

Example 2 — All Heads

$ Input: prob = [0.5, 0.5, 0.5], target = 3

› Output: 0.125

💡 Note: Need all 3 coins to be heads: 0.5 × 0.5 × 0.5 = 0.125

Example 3 — Impossible Target

$ Input: prob = [0.2, 0.3], target = 5

› Output: 0.0

💡 Note: Cannot get 5 heads with only 2 coins, so probability is 0

Constraints

1 ≤ prob.length ≤ 1000
0 ≤ prob[i] ≤ 1
0 ≤ target ≤ prob.length
Answers within 10^-5 of expected answer will be accepted

Visualization

Tap to expand

Understanding the Visualization

Input

Array of coin head probabilities and target count

Process

Calculate probability of all combinations yielding target heads

Output

Sum of probabilities where heads count equals target

Key Takeaway

🎯 Key Insight: Build probability table incrementally - each coin either contributes to heads count or doesn't, and we sum all valid combinations

Asked in

G Google 25 f Facebook 18 M Microsoft 15

The key insight is to use dynamic programming to track probabilities incrementally. For each coin, we can either get heads (with probability prob[i]) or tails (with probability 1-prob[i]). Best approach is Bottom-Up DP with Time: O(n × target), Space: O(n × target).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization - Top Down DP	O(n × target)	O(n × target)	Cache results of subproblems to avoid redundant calculations
Bottom-Up Dynamic Programming	O(n × target)	O(n × target)	Build probability table iteratively from base cases to final answer
Brute Force - All Combinations	O(2^n)	O(n)	Generate all possible outcomes and sum probabilities where heads count equals target

Memoization - Top Down DP — Algorithm Steps

Define recursive function with coin index and remaining heads needed
Use memoization to cache results
For each coin, choose heads or tails and recurse
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

State

(coin_index=0, heads_needed=1)

Branch

Try heads: prob[0] × dp(1,0) and tails: (1-prob[0]) × dp(1,1)

Cache

Store result in memo table for future use

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int index;
    int headsNeeded;
    double prob;
} MemoEntry;

MemoEntry memo[1001][1001];
int memoInit[1001][1001];

double dp(double* prob, int n, int index, int headsNeeded) {
    if (headsNeeded < 0 || headsNeeded > n - index) {
        return 0.0;
    }
    if (index == n) {
        return headsNeeded == 0 ? 1.0 : 0.0;
    }
    
    if (memoInit[index][headsNeeded]) {
        return memo[index][headsNeeded].prob;
    }
    
    // Choose heads
    double headsProb = prob[index] * dp(prob, n, index + 1, headsNeeded - 1);
    // Choose tails
    double tailsProb = (1 - prob[index]) * dp(prob, n, index + 1, headsNeeded);
    
    memo[index][headsNeeded].prob = headsProb + tailsProb;
    memoInit[index][headsNeeded] = 1;
    return memo[index][headsNeeded].prob;
}

double solution(double* prob, int n, int target) {
    memset(memoInit, 0, sizeof(memoInit));
    return dp(prob, n, 0, target);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    double prob[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prob[n++] = atof(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    double result = solution(prob, n, target);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × target)

Each (index, heads_needed) state computed once, n coins × target possible heads

✓ Linear Growth

Space Complexity

O(n × target)

Memoization table stores n × target states plus recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization - Top Down DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler