Given a fair coin that is tossed N times, the task is to determine the probability such that no two heads occur consecutively.
Examples:
Input: N = 2
Output: 0.75
Explanation:
When the coin is tossed 2 times, the possible outcomes are {TH, HT, TT, HH}.
Since in 3 out of 4 outcomes, heads don’t occur together.
Therefore, the required probability is (3/4) or 0.75Input: N = 3
Output: 0.62
Explanation:
When the coin is tossed 3 times, the possible outcomes are {TTT, HTT, THT, TTH, HHT, HTH, THH, HHH}.
Since in 5 out of 8 outcomes, heads don’t occur together.
Therefore, the required probability is (5/8) or 0.62
Approach: The following observation on the number of favorable outcomes has to be made.
- When N = 1: The possible outcomes are {T, H}. There are two favorable outcomes out of the two.
- When N = 2: The possible outcomes are {TH, HT, TT, HH}. There are three favorable outcomes out of four.
- When N = 3: Similarly, the possible outcomes are {TTT, HTT, THT, TTH, HHT, HTH, THH, HHH}. There are five favorable outcomes out of eight.
- When N = 4: Similarly, the possible outcomes are {TTTT, TTTH, TTHT, THTT, HTTT, TTHH, THTH, HTHT, HHTT, THHT, HTTH, THHH, HTHH, HHTH, HHHT, HHHH}. There are eight favorable outcomes out of sixteen.
Clearly, the number of favorable outcomes follow a Fibonacci series where Fn(1) = 2, Fn(2) = 3 and so on. Therefore, the idea is to implement the Fibonacci sequence in order to find the number of favorable cases. Clearly, the total number of cases is 2N.
To calculate the probability, the following formula is used:
P = favorable cases / Total number of cases
Below is the implementation of the above approach:
C++
// C++ implementation to find the // probability of not getting two // consecutive heads together when// N coins are tossed#include <bits/stdc++.h>using namespace std;float round(float var,int digit) { float value = (int)(var * pow(10, digit) + .5); return (float)value / pow(10, digit); }// Function to compute the N-th// Fibonacci number in the // sequence where a = 2 // and b = 3int probability(int N){ // The first two numbers in // the sequence are initialized int a = 2; int b = 3; // Base cases if (N == 1) { return a; } else if(N == 2) { return b; } else { // Loop to compute the fibonacci // sequence based on the first // two initialized numbers for(int i = 3; i <= N; i++) { int c = a + b; a = b; b = c; } return b; }}// Function to find the probability // of not getting two consecutive // heads when N coins are tossedfloat operations(int N) { // Computing the number of // favourable cases int x = probability(N); // Computing the number of // all possible outcomes for // N tosses int y = pow(2, N); return round((float)x / (float)y, 2);} // Driver codeint main(){ int N = 10; cout << (operations(N));}// Thus code is contributed by Rutvik_56 |
Java
// Java implementation to find the // probability of not getting two // consecutive heads together when// N coins are tossedimport java.io.*;class GFG{ public static float round(float var, int digit) { float value = (int)(var * Math.pow(10, digit) + .5); return (float)value / (float)Math.pow(10, digit); } // Function to compute the N-th// Fibonacci number in the // sequence where a = 2 // and b = 3public static int probability(int N){ // The first two numbers in // the sequence are initialized int a = 2; int b = 3; // Base cases if (N == 1) { return a; } else if (N == 2) { return b; } else { // Loop to compute the fibonacci // sequence based on the first // two initialized numbers for(int i = 3; i <= N; i++) { int c = a + b; a = b; b = c; } return b; }} // Function to find the probability // of not getting two consecutive // heads when N coins are tossedpublic static float operations(int N){ // Computing the number of // favourable cases int x = probability(N); // Computing the number of // all possible outcomes for // N tosses int y = (int)Math.pow(2, N); return round((float)x / (float)y, 2);}// Driver codepublic static void main(String[] args) { int N = 10; System.out.println((operations(N)));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation to find the # probability of not getting two # consecutive heads together when# N coins are tossedimport math# Function to compute the N-th# Fibonacci number in the # sequence where a = 2 # and b = 3def probability(N): # The first two numbers in # the sequence are initialized a = 2 b = 3 # Base cases if N == 1: return a elif N == 2: return b else: # Loop to compute the fibonacci # sequence based on the first # two initialized numbers for i in range(3, N + 1): c = a + b a = b b = c return b # Function to find the probability # of not getting two consecutive # heads when N coins are tosseddef operations(N): # Computing the number of # favourable cases x = probability (N) # Computing the number of # all possible outcomes for # N tosses y = math.pow(2, N) return round(x / y, 2)# Driver codeif __name__ == '__main__': N = 10 print(operations(N)) |
C#
// C# implementation to find the // probability of not getting two // consecutive heads together when// N coins are tossedusing System;class GFG{ public static float round(float var, int digit) { float value = (int)(var * Math.Pow(10, digit) + .5); return (float)value / (float)Math.Pow(10, digit); } // Function to compute the N-th// Fibonacci number in the // sequence where a = 2 // and b = 3public static int probability(int N){ // The first two numbers in // the sequence are initialized int a = 2; int b = 3; // Base cases if (N == 1) { return a; } else if (N == 2) { return b; } else { // Loop to compute the fibonacci // sequence based on the first // two initialized numbers for(int i = 3; i <= N; i++) { int c = a + b; a = b; b = c; } return b; }} // Function to find the probability // of not getting two consecutive // heads when N coins are tossedpublic static float operations(int N){ // Computing the number of // favourable cases int x = probability(N); // Computing the number of // all possible outcomes for // N tosses int y = (int)Math.Pow(2, N); return round((float)x / (float)y, 2);}// Driver codepublic static void Main(string[] args) { int N = 10; Console.WriteLine((operations(N)));}}// This code is contributed by chitranayal |
Javascript
<script>// javascript implementation to find the // probability of not getting two // consecutive heads together when// N coins are tossed function round(vr, digit) { var value = parseInt( (vr* Math.pow(10, digit) + .5)); return value / Math.pow(10, digit); } // Function to compute the N-th // Fibonacci number in the // sequence where a = 2 // and b = 3 function probability(N) { // The first two numbers in // the sequence are initialized var a = 2; var b = 3; // Base cases if (N == 1) { return a; } else if (N == 2) { return b; } else { // Loop to compute the fibonacci // sequence based on the first // two initialized numbers for (i = 3; i <= N; i++) { var c = a + b; a = b; b = c; } return b; } } // Function to find the probability // of not getting two consecutive // heads when N coins are tossed function operations(N) { // Computing the number of // favourable cases var x = probability(N); // Computing the number of // all possible outcomes for // N tosses var y = parseInt( Math.pow(2, N)); return round(x / y, 2); } // Driver code var N = 10; document.write((operations(N))); // This code is contributed by aashish1995</script> |
Output:
0.14
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
