Minimizing numbers through subtraction operations
Given two numbers given as P and Q, the task is to make both numbers equal in the minimum number of operations, where you are allowed to perform the below operations any number of times:
- If P > Q, replace P with P − Q;
- If Q < P, replace Q with Q − P.
Examples:
Input: P = 100001, Q = 100001
Output: 0
Explanation: P and Q are equal so no steps are required.Input: P = 10, Q = 18
Output: 5
Explanation: Initially, P=10 and Q=18. You repeat the operation as follows:
- P < Q, so replace Q with Q − P = 8, making P = 10 and Q = 8.
- Q < A, so replace P with P − Q = 2, making P = 2 and Q = 8.
- Q > P, so replace Q with Q − P = 6, making P = 2 and Q = 6.
- Q > P, so replace Q with Q − P = 4, making P = 2 and Q = 4.
- Q > P, so replace Q with Q − P = 2, making P = 2 and Q = 2
Thus, you repeat it five times.
Approach: This can be solved with the following idea:
When Q > P, it means Q/P number of steps would be performed in order to make it equal and vice versa.
Below is the implementation of the above approach:
C++14
// C++ code of the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Minimum Steps required to make both // number equal void minimumSteps( long long P, long long Q) { // Intialize ans = 0; long long number_of_steps = 0; // Already equal if (P == Q) { cout << 0 << endl; return ; } // If not while (P != 0 && Q != 0) { // P is greater than Q if (P > Q) { number_of_steps += P / Q; P = P % Q; } // Q is greater than P else if (Q > P) { number_of_steps += Q / P; Q = Q % P; } } cout << number_of_steps - 1 << endl; } // Driver code int main() { long long P, Q; P = 10; Q = 18; // Function call minimumSteps(P, Q); return 0; } |
Java
// Java code of the above approach import java.util.*; public class GFG { // Function to calculate minimum steps to make two // numbers equal public static void minimumSteps( long P, long Q) { long number_of_steps = 0 ; // If both numbers are already equal, no steps // needed if (P == Q) { System.out.println( 0 ); return ; } // Continue until one of the numbers becomes 0 while (P != 0 && Q != 0 ) { // If P is greater than Q if (P > Q) { // Calculate how many times Q can be // subtracted from P number_of_steps += P / Q; // Update P to the remainder after // subtraction P = P % Q; } // If Q is greater than P else if (Q > P) { // Calculate how many times P can be // subtracted from Q number_of_steps += Q / P; // Update Q to the remainder after // subtraction Q = Q % P; } } // Subtract 1 from the total steps to account for // the final step System.out.println(number_of_steps - 1 ); } public static void main(String[] args) { long P, Q; P = 10 ; Q = 18 ; // Function call minimumSteps(P, Q); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code of the above approach def minimumSteps(P, Q): # Initialize number_of_steps = 0 number_of_steps = 0 # Already equal if P = = Q: print ( 0 ) return # If not equal while P ! = 0 and Q ! = 0 : # P is greater than Q if P > Q: number_of_steps + = P / / Q P = P % Q # Q is greater than P elif Q > P: number_of_steps + = Q / / P Q = Q % P print (number_of_steps - 1 ) # Driver code if __name__ = = '__main__' : P = 10 Q = 18 # Function call minimumSteps(P, Q) |
C#
// C# code of the above approach using System; public class GFG { // Minimum Steps required to make both number equal static void MinimumSteps( long P, long Q) { // Initialize number_of_steps = 0; long number_of_steps = 0; // Already equal if (P == Q) { Console.WriteLine(0); return ; } // If not while (P != 0 && Q != 0) { // P is greater than Q if (P > Q) { number_of_steps += P / Q; P = P % Q; } // Q is greater than P else if (Q > P) { number_of_steps += Q / P; Q = Q % P; } } Console.WriteLine(number_of_steps - 1); } // Driver code static void Main( string [] args) { long P, Q; P = 10; Q = 18; // Function call MinimumSteps(P, Q); } } // This code is contributed by Susobhan Akhuli |
Javascript
<script> // JavaScript code of the above approach // Minimum Steps required to make both // number equal function minimumSteps(P, Q) { // Intialize ans = 0; let number_of_steps = 0; // Already equal if (P == Q) { document.write(0); return ; } // If not while (P != 0 && Q != 0) { // P is greater than Q if (P > Q) { number_of_steps += Math.floor(P / Q); P = P % Q; } // Q is greater than P else if (Q > P) { number_of_steps += Math.floor(Q / P); Q = Q % P; } } document.write(number_of_steps - 1); } // Driver code let P, Q; P = 10; Q = 18; // Function call minimumSteps(P, Q); // This code is contributed by Susobhan Akhuli </script> |
Output
5
Time Complexity: O(Log N)
Auxiliary Space: O(1)
Contact Us