Home
Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
Tags:, , , , , ,

Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm

October 20, 2019 No Comments algorithms, c / c++, DFS, dynamic programming, Dynamic Programming, Knapsack Problems, math, probability

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 1:
Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:
1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Hints:
What about solving the problem with DP?
Use DP with two states dp[pos][cnt], where pos represents the pos-th coin and cnt is the number of heads seen so far.
You can do the transitions with a little bit math.
For the base case, when pos == n return (cnt == target) to filter out the invalid scenarios.

Depth First Search Algorithm to Calculate the Toss Probabilities

Each coin is tossed exactly once, and the probability of overall heads facing up stays the same regardless the order of the coins to toss. We can start at the first coin, imaging a binary tree where the root is the first coin, then the left tree is when the head faces up and the right tree when the head faces down. Therefore, the tree can be depth first search or breadth first search.

When we toss the last coin, we can check if the number of the heads up equal to the target, if yes, we accumulates the probability. We can speed up DFS by abandoning the branches where when we have tossed more than heads we wanted or the current probability is zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        dfs(prob, 0, target, 1);
        return total;
    }
private:
    double total = 0;
    
    void dfs(vector<double>& prob, int index, int target, double cur) {
        if (target < 0) {
            return;
        }
        if (cur == 0) {
            return;
        }
        if (index >= prob.size()) {
            if (target == 0) {
                total += cur;
            }
            return;
        }
        dfs(prob, index + 1, target, cur * (1 - prob[index]));
        dfs(prob, index + 1, target - 1, cur * prob[index]);
    }
};
class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        dfs(prob, 0, target, 1);
        return total;
    }
private:
    double total = 0;
    
    void dfs(vector<double>& prob, int index, int target, double cur) {
        if (target < 0) {
            return;
        }
        if (cur == 0) {
            return;
        }
        if (index >= prob.size()) {
            if (target == 0) {
                total += cur;
            }
            return;
        }
        dfs(prob, index + 1, target, cur * (1 - prob[index]));
        dfs(prob, index + 1, target - 1, cur * prob[index]);
    }
};

However, as the depth of the binary tree can go very deep, the performance may be hit greatly. The complexity is O(2^N) where N is the number of the coins – we may need to traverse all branches/nodes of the binary search tree.

The DFS is the TOP-Down search as we are search from the root (first coin) onwards.

Using Dynamic Programming Algorithm to Compute the Probabilties of Tossing a Coin

We can perform the calculations bottom-up using Dynamic Programming Algorithm. Let dp[i][j] represent the probability of getting j coins facing up after tossing the i-th coin. Therefore, we know that the probability of dp[i][j] can be accumulated from two parts: dp[i – 1][j] and dp[i – 1][j – 1].

For dp[i – 1][j], we have enough j coins facing up, thus for i-th coin, it has to face down – which is 1 – prob[i]. Similarly, for dp[i – 1][j – 1], we have to toss a facing-up coin, which is prob[i]

The initial values:

1
2

dp[0][1] = prob[0];
dp[0][1] = 1 - prob[0];
dp[0][1] = prob[0];
dp[0][1] = 1 - prob[0];

And we have to fill the dp[i][0] values which can be easily pre-computed:

1

dp[i][0] = dp[i - 1][0] * (1 - prob[i]);
dp[i][0] = dp[i - 1][0] * (1 - prob[i]);

The following C++ implements the DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        if (prob.empty()) return 0;
        vector<vector<double>> dp(prob.size(), vector<double>(prob.size() + 1, 0));
        dp[0][1] = prob[0];
        dp[0][0] = 1 - prob[0];
        for (int i = 1; i < prob.size(); ++ i) {
            dp[i][0] = dp[i - 1][0] * (1 - prob[i]);
            for (int j = 1; j <= target; ++ j) {
                dp[i][j] = dp[i - 1][j] * (1 - prob[i]) + dp[i - 1][j - 1] * prob[i];
            }
        }
        return dp[prob.size() - 1][target];
    }
};
class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        if (prob.empty()) return 0;
        vector<vector<double>> dp(prob.size(), vector<double>(prob.size() + 1, 0));
        dp[0][1] = prob[0];
        dp[0][0] = 1 - prob[0];
        for (int i = 1; i < prob.size(); ++ i) {
            dp[i][0] = dp[i - 1][0] * (1 - prob[i]);
            for (int j = 1; j <= target; ++ j) {
                dp[i][j] = dp[i - 1][j] * (1 - prob[i]) + dp[i - 1][j - 1] * prob[i];
            }
        }
        return dp[prob.size() - 1][target];
    }
};

The space requirement is O(N^2) and the time complexity is also O(N^2) where N is the number of the coins.

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system
769 words
Last Post: How to Find the Missing Number In Arithmetic Progression?
Next Post: How to Find the Length of the Longest Increasing Subsequence using Dynamic Programming Algorithm?

The Permanent URL is: Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm

Related posts:

  1. Teaching Kids Programming – 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming) Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a 0-indexed array...
  2. Teaching Kids Programming – Shortest Path Algorithms by Iterative Deepening Search (IDS), Depth First Search (DFS) or Breadth First Search (BFS) on Undirected Graphs Teaching Kids Programming: Videos on Data Structures and Algorithms Shortest Path on Undirected Graphs: DFS...
  3. Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a list of...
  4. Teaching Kids Programming – Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant) Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a list of...
  5. Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms Teaching Kids Programming: Videos on Data Structures and Algorithms Breadth First Search Algorithm (BFS) performs...
  6. Teaching Kids Programming – Minimum Moves to Reach Target Score with Constraints (Greedy Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms You are playing a game with...
  7. Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a two-dimensional list...
  8. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....

Leave a Reply