Given two numbers X and Y, the task is to find the probability that an arbitrary positive divisor of 10X is an integral multiple of 10Y.
Note: Y should be <= X.
Examples:
Input: X = 2, Y = 1
Output: 4/9
Explanation:
Positive divisors of 102 are 1, 2, 4, 5, 10, 20, 25, 50, 100. A total of 9.
Multiples of 101 upto 102 are 10, 20, 50, 100. A total of 4.
P(divisor of 102 is a multiple of 101) = 4/9.
Input: X = 99, Y = 88
Output: 9/625
Explanation:
A = 1099, B = 1088
P(divisor of 1099 is a multiple of 1088) = 9/625
Pre-requisites: Total number of divisors of a number
Approach:
In order to solve the problem, we need to observe the steps below:
- All divisors of 10X will be of the form:
(2 P * 5 Q), where 0 <= P, Q <= X
- Find the number of Prime factors of 10X
10X = 2X * 5X
- Hence, total number of divisors of 10X will be: ( X + 1 ) * ( X + 1 ).
- Now, consider all multiples of 10Y which can be potential divisors of 10X. They are also of the form:
( 2 A * 5 B ), where Y <= A, B <= X.
- So, count of potential divisors of 10X which are also multiples of 10Y is ( X – Y + 1 ) * ( X – Y + 1 ).
- Hence, required probability is (( X – Y + 1 ) * ( X – Y + 1 )) / (( X + 1 ) * ( X + 1 )). Computing the value of the expression for given values of X and Y gives us the required probability.
Below is the implementation of the above approach:
C++
// C++ program to find the probability // of an arbitrary positive divisor of // Xth power of 10 to be a multiple of // Yth power of 10 #include <bits/stdc++.h> using namespace std; #define int long long int // Function to calculate and print // the required probability void prob(int x, int y) { // Count of potential divisors // of X-th power of 10 which are // also multiples of Y-th power // of 10 int num = abs(x - y + 1) * abs(x - y + 1); // Count of divisors of X-th // power of 10 int den = (x + 1) * (x + 1); // Calculate GCD int gcd = __gcd(num, den); // Print the reduced // fraction probability cout << num / gcd << "/" << den / gcd << endl; } // Driver Code signed main() { int X = 2, Y = 1; prob(X, Y); return 0; } |
Java
// Java program to find the probability // of an arbitrary positive divisor of // Xth power of 10 to be a multiple of // Yth power of 10 import java.util.*; class GFG{ // Function to calculate and print // the required probability static void prob(int x, int y) { // Count of potential divisors // of X-th power of 10 which are // also multiples of Y-th power // of 10 int num = Math.abs(x - y + 1) * Math.abs(x - y + 1); // Count of divisors of X-th // power of 10 int den = (x + 1) * (x + 1); // Calculate GCD int gcd = __gcd(num, den); // Print the reduced // fraction probability System.out.print(num / gcd + "/" + den / gcd + "\n"); } static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void main(String[] args) { int X = 2, Y = 1; prob(X, Y); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program to find the probability # of an arbitrary positive divisor of # Xth power of 10 to be a multiple of # Yth power of 10 from math import * # Function to calculate and print # the required probability def prob(x, y): # Count of potential divisors # of X-th power of 10 which are # also multiples of Y-th power # of 10 num = abs(x - y + 1) * abs(x - y + 1) # Count of divisors of X-th # power of 10 den = (x + 1) * (x + 1) # Calculate GCD gcd1 = gcd(num, den) # Print the reduced # fraction probability print(num // gcd1, end = "") print("/", end = "") print(den // gcd1) # Driver Code if __name__ == '__main__': X = 2 Y = 1 prob(X, Y) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find the probability // of an arbitrary positive divisor of // Xth power of 10 to be a multiple of // Yth power of 10 using System; class GFG{ // Function to calculate and print // the required probability static void prob(int x, int y) { // Count of potential divisors // of X-th power of 10 which are // also multiples of Y-th power // of 10 int num = Math.Abs(x - y + 1) * Math.Abs(x - y + 1); // Count of divisors of X-th // power of 10 int den = (x + 1) * (x + 1); // Calculate GCD int gcd = __gcd(num, den); // Print the reduced // fraction probability Console.Write(num / gcd + "/" + den / gcd + "\n"); } static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void Main(string[] args) { int X = 2, Y = 1; prob(X, Y); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript program to find the probability // of an arbitrary positive divisor of // Xth power of 10 to be a multiple of // Yth power of 10 // Function to calculate and print // the required probability function prob(x, y) { // Count of potential divisors // of X-th power of 10 which are // also multiples of Y-th power // of 10 var num = Math.abs(x - y + 1) * Math.abs(x - y + 1); // Count of divisors of X-th // power of 10 var den = (x + 1) * (x + 1); // Calculate GCD var gcd = __gcd(num, den); // Print the reduced // fraction probability document.write(num / gcd + "/" + den / gcd + "\n"); } function __gcd(a, b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Code var X = 2, Y = 1; prob(X, Y); // This code is contributed by Khushboogoyal499 </script> |
Output:
4/9
Time Complexity: O(log(N))
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!
