Given four integers X, Y, P and Q such that X ? Y and gcd(P, Q) = 1. The task is to find minimum operation required to convert X to Y. In a single operation, you can multiply X with either P or Q. If it is not possible to convert X to Y then print -1.
Examples:
Input: X = 12, Y = 2592, P = 2, Q = 3
Output: 6
(12 * 2) -> (24 * 3) -> (72 * 2) -> (144 * 3) -> (432 * 3) -> (1296 * 2) ->2592
Input: X = 7, Y = 9, P = 2, Q = 7
Output: -1
There is no way we can reach 9 from 7 by
multiplying 7 with either 2 or 7
Approach: If Y is not divisible by X then no integral multiplication of any integer with X any number of times can lead to Y and the result is -1.
Else, let d = Y / X. Now, Pa * Qb = d must hold in order to have a valid solution and the result in that case will be (a + b) else -1 if d cannot be expressed in the powers of P and Q.
In order to check the condition, keep dividing d with P and Q until divisible. Now, if d = 1 in the end then the solution is possible else not.
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 minimum// operations requiredint minOperations(int x, int y, int p, int q){ // Not possible if (y % x != 0) return -1; int d = y / x; // To store the greatest power // of p that divides d int a = 0; // While divisible by p while (d % p == 0) { d /= p; a++; } // To store the greatest power // of q that divides d int b = 0; // While divisible by q while (d % q == 0) { d /= q; b++; } // If d > 1 if (d != 1) return -1; // Since, d = p^a * q^b return (a + b);}// Driver codeint main(){ int x = 12, y = 2592, p = 2, q = 3; cout << minOperations(x, y, p, q); return 0;} |
Java
// Java implementation of the approach class GFG{ // Function to return the minimum // operations required static int minOperations(int x, int y, int p, int q) { // Not possible if (y % x != 0) return -1; int d = y / x; // To store the greatest power // of p that divides d int a = 0; // While divisible by p while (d % p == 0) { d /= p; a++; } // To store the greatest power // of q that divides d int b = 0; // While divisible by q while (d % q == 0) { d /= q; b++; } // If d > 1 if (d != 1) return -1; // Since, d = p^a * q^b return (a + b); } // Driver code public static void main (String[] args) { int x = 12, y = 2592, p = 2, q = 3; System.out.println(minOperations(x, y, p, q)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach# Function to return the minimum# operations requireddef minOperations(x, y, p, q): # Not possible if (y % x != 0): return -1 d = y // x # To store the greatest power # of p that divides d a = 0 # While divisible by p while (d % p == 0): d //= p a+=1 # To store the greatest power # of q that divides d b = 0 # While divisible by q while (d % q == 0): d //= q b+=1 # If d > 1 if (d != 1): return -1 # Since, d = p^a * q^b return (a + b)# Driver codex = 12y = 2592p = 2q = 3print(minOperations(x, y, p, q))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System;class GFG{ // Function to return the minimum // operations required static int minOperations(int x, int y, int p, int q) { // Not possible if (y % x != 0) return -1; int d = y / x; // To store the greatest power // of p that divides d int a = 0; // While divisible by p while (d % p == 0) { d /= p; a++; } // To store the greatest power // of q that divides d int b = 0; // While divisible by q while (d % q == 0) { d /= q; b++; } // If d > 1 if (d != 1) return -1; // Since, d = p^a * q^b return (a + b); } // Driver code public static void Main () { int x = 12, y = 2592, p = 2, q = 3; Console.Write(minOperations(x, y, p, q)); }}// This code is contributed by anuj_67.. |
Javascript
<script>// JavaScript implementation of the approach// Function to return the minimum// operations requiredfunction minOperations(x, y, p, q){ // Not possible if (y % x != 0) return -1 var d = Math.floor(y / x) // To store the greatest power // of p that divides d var a = 0 // While divisible by p while (d % p == 0){ d = Math.floor(d / p) a+=1 } // To store the greatest power // of q that divides d var b = 0 // While divisible by q while (d % q == 0){ d = Math.floor(d / q) b+=1 } // If d > 1 if (d != 1) return -1 // Since, d = p^a * q^b return (a + b)}// Driver codevar x = 12var y = 2592var p = 2var q = 3document.write(minOperations(x, y, p, q))// This code is contributed by AnkThon</script> |
6
Auxiliary Space: O(1), since no extra space has been taken
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
