Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  380 
0

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

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.

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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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 ith position, there are two possibilities:

If the number of heads till (i - 1) coins is equal to j then a tail comes at ith. If the number of heads till (i - 1) coins is equal to (j - 1) then a head comes at ith 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 ith 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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a m x n grid filled with non-negative number... >>
<< You are given N eggs, and building with K floors f...