Given four integers p, q, r, and s. Two players are playing a game where both the players hit a target and the first player who hits the target wins the game. The probability of the first player hitting the target is p / q and that of the second player hitting the target is r / s. The task is to find the probability of the first player winning the game.
Examples:
Input: p = 1, q = 4, r = 3, s = 4
Output: 0.307692308Input: p = 1, q = 2, r = 1, s = 2
Output: 0.666666667
Approach: The probability of the first player hitting the target is p / q and missing the target is 1 – p / q.
The probability of the second player hitting the target is r / s and missing the target is 1 – r / s.
Let the first player be x and the second player is y.
So the total probability will be x won + (x lost * y lost * x won) + (x lost * y lost * x lost * y lost * x won) + … so on.
Because x can win at any turn, it’s an infinite sequence.
Let t = (1 – p / q) * (1 – r / s). Here t < 1 as p / q and r / s are always <1.
So the series will become, p / q + (p / q) * t + (p / q) * t2 + …
This is an infinite GP series with a common ratio of less than 1 and its sum will be (p / q) / (1 – t).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the probability of the winnerdouble find_probability(double p, double q, double r, double s){ double t = (1 - p / q) * (1 - r / s); double ans = (p / q) / (1 - t); return ans;}// Driver Codeint main(){ double p = 1, q = 2, r = 1, s = 2; // Will print 9 digits after the decimal point cout << fixed << setprecision(9) << find_probability(p, q, r, s); return 0;} |
Java
// Java implementation of the approachimport java.util.*;import java.text.DecimalFormat;class solution{// Function to return the probability of the winnerstatic double find_probability(double p, double q, double r, double s){ double t = (1 - p / q) * (1 - r / s); double ans = (p / q) / (1 - t); return ans;}// Driver Codepublic static void main(String args[]){ double p = 1, q = 2, r = 1, s = 2; // Will print 9 digits after the decimal point DecimalFormat dec = new DecimalFormat("#0.000000000"); System.out.println(dec.format(find_probability(p, q, r, s)));}}// This code is contributed by// Surendra_Gangwar |
Python3
# Python3 implementation of the approach # Function to return the probability# of the winner def find_probability(p, q, r, s) : t = (1 - p / q) * (1 - r / s) ans = (p / q) / (1 - t); return round(ans, 9)# Driver Code if __name__ == "__main__" : p, q, r, s = 1, 2, 1, 2 # Will print 9 digits after # the decimal point print(find_probability(p, q, r, s)) # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the probability of the winnerstatic double find_probability(double p, double q, double r, double s){ double t = (1 - p / q) * (1 - r / s); double ans = (p / q) / (1 - t); return ans;}// Driver Codepublic static void Main(){ double p = 1, q = 2, r = 1, s = 2; Console.WriteLine(find_probability(p, q, r, s));}}// This code is contributed by// anuj_67.. |
PHP
<?php// PHP implementation of the approach// Function to return the probability// of the winnerfunction find_probability($p, $q, $r, $s){ $t = (1 - $p / $q) * (1 - $r / $s); $ans = ($p / $q) / (1 - $t); return $ans;}// Driver Code$p = 1; $q = 2;$r = 1; $s = 2;// Will print 9 digits after // the decimal point$res = find_probability($p, $q, $r, $s);$update = number_format($res, 7);echo $update;// This code is contributed by Rajput-Ji?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the probability of the winnerfunction find_probability(p, q, r, s){ var t = (1 - p / q) * (1 - r / s); var ans = (p / q) / (1 - t); return ans;}// Driver Codevar p = 1, q = 2, r = 1, s = 2;// Will print 9 digits after the decimal pointdocument.write( find_probability(p, q, r, s).toFixed(9));</script> |
0.666666667
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
