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 N coins, numbered 1, 2 , ... , N. For each i (1≤i≤N), when Coin i is tossed, it comes up heads with probability pi and tails with probability 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.

Explanation with example

    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 j heads with first i coins. To get j heads at the i^th position, there are two possibilities:

If the number of heads till (i - 1) coins is equal to j then a tail comes at i^th. If the number of heads till (i - 1) coins is equal to (j - 1) then a head comes at i^th position.

The probability of occurring jth head at ith coin toss depends on the number of heads in (i-1)^th coins, if (i-1) coin have (j-1) head then jth coin occurs at i^th coin(p[i]), and if (i-1) coins have already j coins then at jth toss tails come(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