Probability of hitting the target Nth time at Mth throw
Given integers N, M and p, the task is to find the probability of hitting a target for the Nth time at the Mth throw where p is the probability of hitting the target.
Examples:
Input: N = 1, M = 2, p = 0.3
Output: 0.21
Explanation: The target can be hit for the first time in the second throw only when the first throw is a miss.
So, the probability is multiplication of probability of hitting the target in second throw and probability of missing the target in the first throw = 0.3 * 0.7 = 0.21
because probability of missing = 1 β probability of hitting.Input: N = 8, M = 17, p = 0.4,
Output: 0.07555569565040642
Approach: The idea to solve the problem is based on the binomial distribution of probability
For getting Nth hit in the Mth throw there must be N-1 hits in the M-1 throws earlier and Nth throw must be a hit.
Say p is the probability of hitting and q is the probability of missing. q = 1 β p.
So the probability of getting N-1 hits in M-1 throws is:
X = M-1CN-1 (pN-1qM-1-(N-1)) = M-1CN-1 (pN-1qM-N)
Therefore, the probability of hitting for Nth time is p*X = M-1CN-1 (pNqM-N)
Follow the below steps to implement the above idea:
- Firstly, get the probability of not hitting a target.
- Get the value of X as shown above.
- Multiply the value of βpβ with it to get the actual answer.
Below is the implementation of the above approach.
C++
// Cpp code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the factorial of a number int fact( int f) { int fact = 1; for ( int i = 1; i <= f; i++) fact = i * fact; return fact; } // Function to find the probability // of Nth hit at Mth throw double probab( double p, int m, int n) { double q = 1 - p; double res = fact(m - 1) / fact(n - 1) / fact(m - n) * pow (p, (n - 1)) * pow (q, (m - n)) * p; return res; } // Driver code int main() { double p = 0.3; int M = 2; int N = 1; // Function call cout << probab(p, M, N); return 0; } // This code is contributed by ANKITKUMAR34. |
Java
// Java code for above approach import java.util.*; class GFG { // Function to find the factorial of a number public static int fact( int f) { int fact = 1 ; for ( int i = 1 ; i <= f; i++) fact = i * fact; return fact; } // Function to find the probability // of Nth hit at Mth throw public static double probab( double p, int m, int n) { double q = 1 - p; double res = fact(m - 1 ) / fact(n - 1 ) / fact(m - n) * Math.pow(p, (n - 1 )) * Math.pow(q, (m - n)) * p; return res; } // Driver code public static void main(String[] args) { double p = 0.3 ; int M = 2 ; int N = 1 ; // Function call System.out.println(probab(p, M, N)); } } // This code is contributed by Pushpesh Raj. |
Python3
# Python code to implement the approach # Function to find the probability # of Nth hit at Mth throw def probab(p, m, n): q = 1 - p res = fact(m - 1 ) / fact(n - 1 ) / fact(m - n) * p * * (n - 1 ) * q * * (m - n) * p return res # Function to find the factorial of a number def fact(f): fact = 1 for i in range ( 1 , f + 1 ): fact = i * fact return fact # Driver code if __name__ = = '__main__' : p = 0.3 M = 2 N = 1 # Function call print (probab(p, M, N)) |
C#
// C# code for above approach using System; public class GFG { // Function to find the factorial of a number public static int fact( int f) { int fact = 1; for ( int i = 1; i <= f; i++) fact = i * fact; return fact; } // Function to find the probability // of Nth hit at Mth throw public static double probab( double p, int m, int n) { double q = 1 - p; double res = fact(m - 1) / fact(n - 1) / fact(m - n) * Math.Pow(p, (n - 1)) * Math.Pow(q, (m - n)) * p; return res; } // Driver code public static void Main( string [] args) { double p = 0.3; int M = 2; int N = 1; // Function call Console.WriteLine(probab(p, M, N)); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript code to implement the approach // Function to find the factorial of a number function fact(f) { let fact = 1; for (let i=1; i<=f; i++ ) fact = i * fact; return fact; } // Function to find the probability //of Nth hit at Mth throw function probab(p, m, n) { let q = 1-p; let res = fact(m-1) / fact(n-1) / fact(m-n) * Math.pow(p, (n-1)) * Math.pow(q, (m-n)) * p; return res; } // Driver code let p = 0.3; let M = 2; let N = 1; // Function call document.write(probab(p, M, N)) // This code is contributed by Saurabh Jaiswal </script> |
0.21
Time Complexity: O(M)
Auxiliary Space: O(1)
Approach:
- Start by defining a function binomialCoeff(M, N) to calculate the binomial coefficient C(M, N). This function can be implemented using recursion.
- If N is 0 or N is equal to M, return 1 (base cases).
- Otherwise, return the sum of binomialCoeff(M β 1, N β 1) and binomialCoeff(M β 1, N) (recursive cases).
- Define a function probab(p, M, N) to calculate the probability. This function takes the probability of hitting the target p, the total number of throws M, and the target hit on the Nth throw N as inputs.
- Calculate the binomial coefficient C(M β 1, N β 1) by calling the binomialCoeff function.
- Calculate p^N using the power function pow(p, N).
- Calculate (1 β p)^(M β N) using the power function pow(1 β p, M β N).
- Multiply the binomial coefficient, p^N, and (1 β p)^(M β N) to get the probability.
- Return the calculated probability.
Below is the implementation of this approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to calculate the binomial coefficient C(M, N) int binomialCoeff( int M, int N) { if (N == 0 || N == M) return 1; return binomialCoeff(M - 1, N - 1) + binomialCoeff(M - 1, N); } // Function to calculate the probability of Nth hit at Mth throw double probab( double p, int M, int N) { double probability = binomialCoeff(M - 1, N - 1) * pow (p, N) * pow (1 - p, M - N); return probability; } // Driver code int main() { double p = 0.3; int M = 2; int N = 1; // Function call cout << probab(p, M, N); return 0; } |
Java
import java.util.*; public class Main { // Function to calculate the binomial coefficient C(M, N) public static int binomialCoeff( int M, int N) { if (N == 0 || N == M) { return 1 ; } return binomialCoeff(M - 1 , N - 1 ) + binomialCoeff(M - 1 , N); } // Function to calculate the probability of Nth hit at Mth throw public static double probab( double p, int M, int N) { double probability = binomialCoeff(M - 1 , N - 1 ) * Math.pow(p, N) * Math.pow( 1 - p, M - N); return probability; } // Driver code public static void main(String[] args) { double p = 0.3 ; int M = 2 ; int N = 1 ; // Function call System.out.println(probab(p, M, N)); } } |
Python
import math # Function to calculate the binomial coefficient C(M, N) def binomial_coeff(m, n): if n = = 0 or n = = m: return 1 return binomial_coeff(m - 1 , n - 1 ) + binomial_coeff(m - 1 , n) # Function to calculate the probability of Nth hit at Mth throw def probab(p, m, n): probability = binomial_coeff(m - 1 , n - 1 ) * math. pow (p, n) * math. pow ( 1 - p, m - n) return probability def main(): p = 0.3 m = 2 n = 1 print (probab(p, m, n)) if __name__ = = "__main__" : main() |
C#
using System; public class GFG { // Function to calculate the binomial coefficient C(M, N) public static int BinomialCoeff( int M, int N) { if (N == 0 || N == M) return 1; return BinomialCoeff(M - 1, N - 1) + BinomialCoeff(M - 1, N); } // Function to calculate the probability of Nth hit at Mth throw public static double Probability( double p, int M, int N) { double probability = BinomialCoeff(M - 1, N - 1) * Math.Pow(p, N) * Math.Pow(1 - p, M - N); return probability; } // Driver code public static void Main( string [] args) { double p = 0.3; int M = 2; int N = 1; // Function call Console.WriteLine(Probability(p, M, N)); } } |
Javascript
// Function to calculate the binomial coefficient C(M, N) function binomialCoeff(M, N) { if (N === 0 || N === M) { return 1; } return binomialCoeff(M - 1, N - 1) + binomialCoeff(M - 1, N); } // Function to calculate the probability of Nth hit at Mth throw function probab(p, M, N) { const probability = binomialCoeff(M - 1, N - 1) * Math.pow(p, N) * Math.pow(1 - p, M - N); return probability; } // Driver code const p = 0.3; const M = 2; const N = 1; // Function call console.log(probab(p, M, N)); |
0.21
Time Complexity: O(2^M), where M is the total number of throws.
Auxiliary Space: O(M)