Horje
Minimize operations to reduce A or B to 0 by reducing A from B or B from A

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=1

Input: 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 Code
int main()
{
 
    int A = 5, B = 4;
    cout << countOperations(A, B);
    return 0;
}

Java

// Java program to find Minimum number
import 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 approach
def countOperations(num1, num2):
    cnt = 0
    while (num1 > 0 and num2 > 0):
        if (num1 >= num2):
            num1 -= num2
        else:
            num2 -= num1
        cnt += 1
 
    return cnt
 
# Driver Code
A,B = 5,4
print(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 Zero
using 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)

 


 


Reffered: https://www.geeksforgeeks.org

Greedy

Related
Maximum power in N levels from K such that defeating boss at level A[i] increases power by B[i] Maximum power in N levels from K such that defeating boss at level A[i] increases power by B[i]
Check if given Array can be reduced to 0 by removing element less than K and adding it to K Check if given Array can be reduced to 0 by removing element less than K and adding it to K
Check if CPU will process given requests successfully or not Check if CPU will process given requests successfully or not
Minimal distance such that for every customer there is at least one vendor at given distance Minimal distance such that for every customer there is at least one vendor at given distance
Maximize the value left after reducing the Arrays based on given conditions Maximize the value left after reducing the Arrays based on given conditions

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje