Home » Interview coding problems/challenges

# Probability of getting more number of heads than tails if coins are tossed

**Probability of Head Coins**: Here, we are going to learn **how to find the probability of getting more number of heads than tails if coins are tossed using dynamic programming approach?** This is a very popular coding problem which has been featured in interview rounds of many big companies such as Paytm, Zomato, Amazon etc.

Submitted by Divyansh Jaipuriyar, on April 29, 2020

**Problem statement:**

Let * N* be a positive odd number. There are

*coins, numbered*

**N***. For each*

**1, 2 , ... , N***(*

**i***1≤i≤N*), when Coin

*is tossed, it comes up heads with probability*

**i***and tails with probability*

**pi***.*

**1-pi**Find the probability of having more heads than tails if coins are tossed.

**Input:**

The first line contains * N*, number of coins. The second line contains the probability of coming head in the coins.

**Output:**

Output the probability of having more number of heads than tails if coins are tossed.

**Example with explanation:**

Input: N=3 [0.30, 0.60, 0.80] Output: 0.612 The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Head) is 0.3×0.6×0.8 = 0.144; The probability of having (Coin1,Coin2,Coin3) = (Tail,Head,Head) is 0.7×0.6×0.8 = 0.336; The probability of having (Coin1,Coin2,Coin3) = (Head,Tail,Head) is 0.3×0.4×0.8 = 0.096; The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Tail) is 0.3×0.6×0.2 = 0.036 Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612

**Solution Approach**

**Dynamic Programming**

Since the problem can be solved with recursion with time complexity of * O(2^n)* which is not accepted as there are other better approach to solve the problem with time complexity of

*;*

**O(n*n)**Let's assume * prob[i][j]* to be the probability of getting

*heads with first*

**j***coins. To get*

**i***heads at the*

**j***position, there are two possibilities:*

**i**^{th}If the number of heads till * (i - 1)* coins is equal to

*then a tail comes at*

**j***. If the number of heads till*

**i**^{th}*coins is equal to*

**(i - 1)***then a head comes at*

**(j - 1)***position.*

**i**^{th}The probability of occurring jth head at ith coin toss depends on the number of heads in * (i-1)^{th}* coins, if

*coin have*

**(i-1)***head then*

**(j-1)***coin occurs at*

**jth***coin(*

**i**^{th}*), and if*

**p[i]***coins have already*

**(i-1)***coins then at*

**j***toss tails come(*

**jth***).*

**1-p[i]****Pseudo Code:**

// p[] is the probability array, // n is the size of array. solve(p[],n): // declare prob[n+1][n+1] array of having required head. prob[n+1][n+1] // no head out of 1 coins prob[1][0]=1-p[0] // one head out of one coins prob[1][1]=p[0] for(i=2;i<=n;i++) // probability of having no heads. prob[i][0]=prob[i-1][0]*(1-p[i]) for(i=2;i<=n;i++) for(j=1;j<=i;j++) prob[i][j]=prob[i-1][j-1]*p[i-1]+prob[i-1][j]*(1-p[i-1]) // probability of having jth head can take // place in (i-1) coins or at (i)th coin. sum=0 for(i=n/2+n%2;i<=n;i++) //probability of heads>tails. sum+=prob[n][i] return sum

**Time complexity**: In worst case **O(n*n)**

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; typedef double ll; int main() { cout << "Enter number of test cases: "; int t; cin >> t; while (t--) { cout << "Enter the number of coins: "; int n; cin >> n; ll p[n]; cout << "Enter the probabilities of head: "; for (int i = 0; i < n; i++) cin >> p[i]; ll prob[n + 1][n + 1]; // probability of one heads with one coins prob[1][1] = p[0]; // probability of no heads with one coins prob[1][0] = 1 - p[0]; for (int i = 2; i <= n; i++) // probability of no heads with i coins. prob[i][0] = prob[i - 1][0] * (1 - p[i - 1]); for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) // probability of head at ith coin it it occurs at(i-1) // then just multiply with tail probability otherwise // multiply with head probability. prob[i][j] = prob[i - 1][j - 1] * p[i - 1] + prob[i - 1][j] * (1 - p[i - 1]); } ll sum = 0; for (int i = n / 2 + n % 2; i <= n; i++) // take those probability which have more heads than tails. sum += prob[n][i]; cout << "The probability of heads more than the tails is: "; cout << setprecision(10) << sum << "\n"; } return 0; }

**Output**

Enter number of test cases: 3 Enter the number of coins: 5 Enter the probabilities of head: 0.42 0.01 0.42 0.99 0.42 The probability of heads more than the tails is: 0.3821815872 Enter the number of coins: 3 Enter the probabilities of head: 0.30 0.60 0.80 The probability of heads more than the tails is: 0.612 Enter the number of coins: 1 Enter the probabilities of head: 0.50 The probability of heads more than the tails is: 0.5

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions