Given two numbers A and B, the task is to find the minimum number of operations required to reduce either A or B to 0, wherein each operation A can be reduced by B if A is greater than equal to B, or vice versa.
Examples:
Input: A = 5, B = 4
Output: 5
Explanation:
Reduce B from A: A=1, B=4
Reduce A from B: A=1, B=3
Reduce A from B: A=1, B=2
Reduce A from B: A=1, B=1
Reduce B from A: A=0, B=1Input: A=1, B=1
Output: 1
Explanation:
Reduce A from B: A=0, B=0
Approach: The approach to solving this problem is simply to check for bigger numbers and reduce the small number from it.
- Repeat following operations till at least one of the two numbers become 0
- If A is greater than equal to B, reduce B from A
- If A is smaller than A, reduce A from B
- For each loop iteration, store the count.
- Return the count of loop iterations at the end.
Below is the implementation of the above approach:
C++
// C++ program to find Minimum number// Of operations required to reduce// Either A or B to Zero#include <iostream>using namespace std;int countOperations(int num1, int num2){ int cnt = 0; while (num1 > 0 && num2 > 0) { if (num1 >= num2) num1 -= num2; else num2 -= num1; cnt++; } return cnt;}// Driver Codeint main(){ int A = 5, B = 4; cout << countOperations(A, B); return 0;} |
Java
// Java program to find Minimum numberimport java.io.*;class GFG { // Of operations required to reduce // Either A or B to Zero static int countOperations(int num1, int num2) { int cnt = 0; while (num1 > 0 && num2 > 0) { if (num1 >= num2) num1 -= num2; else num2 -= num1; cnt++; } return cnt; } // Driver Code public static void main (String[] args) { int A = 5, B = 4; System.out.println(countOperations(A, B)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approachdef countOperations(num1, num2): cnt = 0 while (num1 > 0 and num2 > 0): if (num1 >= num2): num1 -= num2 else: num2 -= num1 cnt += 1 return cnt# Driver CodeA,B = 5,4print(countOperations(A, B))# This code is contributed by shinjanpatra |
C#
// C# program to find Minimum number// Of operations required to reduce// Either A or B to Zerousing System;class GFG { static int countOperations(int num1, int num2) { int cnt = 0; while (num1 > 0 && num2 > 0) { if (num1 >= num2) num1 -= num2; else num2 -= num1; cnt++; } return cnt; } // Driver Code public static void Main() { int A = 5, B = 4; Console.Write(countOperations(A, B)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach function countOperations(num1, num2) { let cnt = 0; while (num1 > 0 && num2 > 0) { if (num1 >= num2) num1 -= num2; else num2 -= num1; cnt++; } return cnt; } // Driver Code let A = 5, B = 4; document.write(countOperations(A, B)); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: 0(MAX(A, B)), where A and B are the two numbers given.
Auxiliary Space: 0(1)
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!
Share your thoughts in the comments
