Given three positive integers M, X, and Y, the task is to find the minimum number of operations required to make X and Y equal such that in each operation divide X or Y by one of its prime factor less than M. If it is not possible to make X and Y equal, then print “-1”.
Examples:
Input: X = 20, Y =16, M = 10
Output: 3
Explanation:
Perform the operation on X and Y as illustrate below:
X: 20 -> 4 : 20/5 = 4
Y: 16 -> 8 : 16/ 2 = 8, 8 -> 4 : 8/2 = 4
Therefore, the total number of steps required to make X and Y equal is 3.Input: X =160, Y = 180, M = 10
Output: 5
Approach: The idea to solve the given problem is based on the observation that the value at which both X and Y are equal is the GCD of X and Y. Follow the steps below to solve the problem:
- Precalculate all prime factors of the numbers till 106 using Sieve of Eratosthenes and store it in an array.
- Calculate GCD of the numbers X and Y and store their value in a variable, say GCD.
- Now, count the number of prime factors in X / GCD and Y / GCD. If any prime factor has a value greater than M, then it is not possible to make X and Y equal. Therefore, print “-1”.
- Otherwise, print the sum number of primes in X / GCD and Y / GCD as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the prime factor of numbersint primes[1000006];// Function to find GCD of a and bint gcd(int a, int b){ // Base Case if (b == 0) return a; // Otherwise, calculate GCD else return gcd(b, a % b);}// Function to precompute the// prime numbers till 1000000void preprocess(){ // Initialize all the positions // with their respective values for(int i = 1; i <= 1000000; i++) primes[i] = i; // Iterate over the range [2, sqrt(10^6)] for(int i = 2; i * i <= 1000000; i++) { // If i is prime number if (primes[i] == i) { // Mark it as the factor for(int j = 2 * i; j <= 1000000; j += i) { if (primes[j] == j) primes[j] = i; } } }}// Utility function to count the number// of steps to make X and Y equalint Steps(int x, int m){ // Initialise steps int steps = 0; bool flag = false; // Iterate x is at most 1 while (x > 1) { if (primes[x] > m) { flag = true; break; } // Divide with the // smallest prime factor x /= primes[x]; steps++; } // If X and Y can't be // made equal if (flag) return -1; // Return steps return steps;}// Function to find the minimum number of// steps required to make X and Y equalint minimumSteps(int x, int y, int m){ // Generate all the prime factors preprocess(); // Calculate GCD of x and y int g = gcd(x, y); // Divide the numbers by their gcd x = x / g; y = y / g; int x_steps = Steps(x, m); int y_steps = Steps(y, m); // If not possible, then return -1; if (x_steps == -1 || y_steps == -1) return -1; // Return the resultant number of steps return x_steps + y_steps;}// Driver Codeint main(){ int X = 160; int Y = 180; int M = 10; cout << (minimumSteps(X, Y, M));}// This code is contributed by chitranayal |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Stores the prime factor of numbers static int primes[] = new int[1000006]; // Function to find GCD of a and b static int gcd(int a, int b) { // Base Case if (b == 0) return a; // Otherwise, calculate GCD else return gcd(b, a % b); } // Function to precompute the // prime numbers till 1000000 static void preprocess() { // Initialize all the positions // with their respective values for (int i = 1; i <= 1000000; i++) primes[i] = i; // Iterate over the range [2, sqrt(10^6)] for (int i = 2; i * i <= 1000000; i++) { // If i is prime number if (primes[i] == i) { // Mark it as the factor for (int j = 2 * i; j <= 1000000; j += i) { if (primes[j] == j) primes[j] = i; } } } } // Utility function to count the number // of steps to make X and Y equal static int Steps(int x, int m) { // Initialise steps int steps = 0; boolean flag = false; // Iterate x is at most 1 while (x > 1) { if (primes[x] > m) { flag = true; break; } // Divide with the // smallest prime factor x /= primes[x]; steps++; } // If X and Y can't be // made equal if (flag) return -1; // Return steps return steps; } // Function to find the minimum number of // steps required to make X and Y equal static int minimumSteps(int x, int y, int m) { // Generate all the prime factors preprocess(); // Calculate GCD of x and y int g = gcd(x, y); // Divide the numbers by their gcd x = x / g; y = y / g; int x_steps = Steps(x, m); int y_steps = Steps(y, m); // If not possible, then return -1; if (x_steps == -1 || y_steps == -1) return -1; // Return the resultant number of steps return x_steps + y_steps; } // Driver Code public static void main(String args[]) { int X = 160; int Y = 180; int M = 10; System.out.println( minimumSteps(X, Y, M)); }} |
Python3
# Python program for the above approach# Stores the prime factor of numbersprimes = [0] * (1000006)# Function to find GCD of a and bdef gcd(a, b) : # Base Case if (b == 0) : return a # Otherwise, calculate GCD else : return gcd(b, a % b)# Function to precompute the# prime numbers till 1000000def preprocess() : # Initialize all the positions # with their respective values for i in range(1, 1000001): primes[i] = i # Iterate over the range [2, sqrt(10^6)] i = 2 while(i * i <= 1000000) : # If i is prime number if (primes[i] == i) : # Mark it as the factor for j in range(2 * i, 1000001, i): if (primes[j] == j) : primes[j] = i i += 1# Utility function to count the number# of steps to make X and Y equaldef Steps(x, m) : # Initialise steps steps = 0 flag = False # Iterate x is at most 1 while (x > 1) : if (primes[x] > m) : flag = True break # Divide with the # smallest prime factor x //= primes[x] steps += 1 # If X and Y can't be # made equal if (flag != 0) : return -1 # Return steps return steps# Function to find the minimum number of# steps required to make X and Y equaldef minimumSteps(x, y, m) : # Generate all the prime factors preprocess() # Calculate GCD of x and y g = gcd(x, y) # Divide the numbers by their gcd x = x // g y = y // g x_steps = Steps(x, m) y_steps = Steps(y, m) # If not possible, then return -1 if (x_steps == -1 or y_steps == -1) : return -1 # Return the resultant number of steps return x_steps + y_steps# Driver CodeX = 160Y = 180M = 10print(minimumSteps(X, Y, M))# This code is contributed by souravghosh0416. |
C#
// C# program for the above approachusing System;class GFG{// Stores the prime factor of numbersstatic int[] primes = new int[1000006];// Function to find GCD of a and bstatic int gcd(int a, int b){ // Base Case if (b == 0) return a; // Otherwise, calculate GCD else return gcd(b, a % b);}// Function to precompute the// prime numbers till 1000000static void preprocess(){ // Initialize all the positions // with their respective values for(int i = 1; i <= 1000000; i++) primes[i] = i; // Iterate over the range [2, sqrt(10^6)] for(int i = 2; i * i <= 1000000; i++) { // If i is prime number if (primes[i] == i) { // Mark it as the factor for(int j = 2 * i; j <= 1000000; j += i) { if (primes[j] == j) primes[j] = i; } } }}// Utility function to count the number// of steps to make X and Y equalstatic int Steps(int x, int m){ // Initialise steps int steps = 0; bool flag = false; // Iterate x is at most 1 while (x > 1) { if (primes[x] > m) { flag = true; break; } // Divide with the // smallest prime factor x /= primes[x]; steps++; } // If X and Y can't be // made equal if (flag) return -1; // Return steps return steps;}// Function to find the minimum number of// steps required to make X and Y equalstatic int minimumSteps(int x, int y, int m){ // Generate all the prime factors preprocess(); // Calculate GCD of x and y int g = gcd(x, y); // Divide the numbers by their gcd x = x / g; y = y / g; int x_steps = Steps(x, m); int y_steps = Steps(y, m); // If not possible, then return -1; if (x_steps == -1 || y_steps == -1) return -1; // Return the resultant number of steps return x_steps + y_steps;}// Driver codestatic void Main() { int X = 160; int Y = 180; int M = 10; Console.Write(minimumSteps(X, Y, M));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach // Stores the prime factor of numbers var primes = Array(1000006).fill(0); // Function to find GCD of a and b function gcd(a , b) { // Base Case if (b == 0) return a; // Otherwise, calculate GCD else return gcd(b, a % b); } // Function to precompute the // prime numbers till 1000000 function preprocess() { // Initialize all the positions // with their respective values for (i = 1; i <= 1000000; i++) primes[i] = i; // Iterate over the range [2, sqrt(10^6)] for (i = 2; i * i <= 1000000; i++) { // If i is prime number if (primes[i] == i) { // Mark it as the factor for (j = 2 * i; j <= 1000000; j += i) { if (primes[j] == j) primes[j] = i; } } } } // Utility function to count the number // of steps to make X and Y equal function Steps(x , m) { // Initialise steps var steps = 0; var flag = false; // Iterate x is at most 1 while (x > 1) { if (primes[x] > m) { flag = true; break; } // Divide with the // smallest prime factor x /= primes[x]; steps++; } // If X and Y can't be // made equal if (flag) return -1; // Return steps return steps; } // Function to find the minimum number of // steps required to make X and Y equal function minimumSteps(x , y , m) { // Generate all the prime factors preprocess(); // Calculate GCD of x and y var g = gcd(x, y); // Divide the numbers by their gcd x = x / g; y = y / g; var x_steps = Steps(x, m); var y_steps = Steps(y, m); // If not possible, then return -1; if (x_steps == -1 || y_steps == -1) return -1; // Return the resultant number of steps return x_steps + y_steps; } // Driver Code var X = 160; var Y = 180; var M = 10; document.write(minimumSteps(X, Y, M));// This code contributed by umadevi9616</script> |
Output:
5
Time Complexity: O(N log N)
Auxiliary Space: O(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!
