# Count Operations to Obtain Zero
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-operations-to-obtain-zero)
Canonical: https://scaleengineer.com/dsa/problems/count-operations-to-obtain-zero
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Capital One](https://scaleengineer.com/companies/capital-one), [PayU](https://scaleengineer.com/companies/payu)
---
## Problem
You are given two **non-negative** integers `num1` and `num2`.

In one **operation**, if `num1 >= num2`, you must subtract `num2` from `num1`, otherwise subtract `num1` from `num2`.

* For example, if `num1 = 5` and `num2 = 4`, subtract `num2` from `num1`, thus obtaining `num1 = 1` and `num2 = 4`. However, if `num1 = 4` and `num2 = 5`, after one operation, `num1 = 4` and `num2 = 1`.

Return _the **number of operations** required to make either_ `num1 = 0` _or_ `num2 = 0`.

**Example 1:**

**Input:** num1 = 2, num2 = 3
**Output:** 3
**Explanation:** 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

**Example 2:**

**Input:** num1 = 10, num2 = 10
**Output:** 1
**Explanation:** 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

**Constraints:**

* `0 <= num1, num2 <= 105`

# Approaches
## Simple Simulation using Subtraction
This is a straightforward approach that directly simulates the process described in the problem. We repeatedly subtract the smaller number from the larger number in a loop and count how many times we perform this operation until one of the numbers becomes zero.
**Time:** O(max(num1, num2)) - In the worst-case scenario (e.g., one number is 1), the number of operations is proportional to the larger number. Let N = max(num1, num2) and M = min(num1, num2), the complexity is roughly O(N/M * M) in some cases, but a simpler upper bound is O(N). · **Space:** O(1) - We only use a few variables to store the current numbers and the operation count, so the space required is constant.
**Pros:** Very simple to understand and implement.; Directly translates the problem description into code.
**Cons:** This approach can be very slow if one number is much larger than the other. For instance, if `num1 = 100000` and `num2 = 1`, it would take 100000 operations.; May result in a 'Time Limit Exceeded' (TLE) error for larger inputs within the given constraints.
### Explanation
The algorithm maintains a loop that runs as long as neither of the two numbers is zero. In each step of the loop, it checks which number is larger and performs the subtraction accordingly. A counter is incremented for each subtraction. This process is identical to the Euclidean algorithm using subtraction.

```java
class Solution {
    public int countOperations(int num1, int num2) {
        int operations = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) {
                num1 = num1 - num2;
            } else {
                num2 = num2 - num1;
            }
            operations++;
        }
        return operations;
    }
}
```
### Algorithm
- Initialize a counter `operations` to 0.
- Use a `while` loop that continues as long as both `num1` and `num2` are greater than 0.
- Inside the loop, compare `num1` and `num2`.
- If `num1 >= num2`, subtract `num2` from `num1`.
- Otherwise, subtract `num1` from `num2`.
- Increment the `operations` counter in each iteration.
- The loop terminates when one of the numbers becomes 0. Return the `operations` count.

## Optimized Recursive Simulation using Division
This approach optimizes the simulation by recognizing that a series of subtractions is equivalent to a division operation. For example, subtracting 3 from 10 repeatedly is the same as finding `10 / 3` (which is 3 operations) and the new number being `10 % 3`. This method is implemented recursively, which can lead to more concise code.
**Time:** O(log(min(num1, num2))) - The number of recursive calls is very small compared to the input values, following the time complexity of the Euclidean algorithm. · **Space:** O(log(min(num1, num2))) - The depth of the recursion is determined by the number of steps in the Euclidean algorithm, which is logarithmic. Each recursive call adds a frame to the call stack.
**Pros:** Significantly more time-efficient than the simple subtraction method.; The recursive solution is often considered elegant and can be easier to reason about.
**Cons:** Uses extra space on the call stack due to recursion. For very large numbers (beyond the problem's constraints), this could lead to a stack overflow.; Slightly less space-efficient than the iterative equivalent.
### Explanation
The core idea is to replace multiple subtractions with a single division and modulo operation. This is the principle behind the Euclidean algorithm. The number of operations in a single step is the integer quotient of the larger number divided by the smaller one. The recursion then continues with the smaller number and the remainder. This drastically reduces the number of steps required.

```java
class Solution {
    public int countOperations(int num1, int num2) {
        // Base case: if one number is 0, no more operations needed.
        if (num1 == 0 || num2 == 0) {
            return 0;
        }

        // Recursive step
        if (num1 >= num2) {
            return (num1 / num2) + countOperations(num1 % num2, num2);
        } else {
            return (num2 / num1) + countOperations(num1, num2 % num1);
        }
    }
}
```
### Algorithm
- This approach is based on the Euclidean algorithm, which uses division and modulo operations to speed up the process.
- Define a recursive function that takes `num1` and `num2` as input.
- The base case for the recursion is when either number is 0, in which case we return 0 operations.
- In the recursive step, we ensure `num1` is the larger number (swapping if necessary).
- We calculate how many times `num2` can be subtracted from `num1` in one go, which is `quotient = num1 / num2`.
- The new state of the numbers becomes `(num2, num1 % num2)`.
- The result is the sum of the `quotient` and the result of the recursive call with the new numbers: `quotient + countOperations(num2, num1 % num2)`.

## Optimized Iterative Simulation using Division
This is the most optimal approach, combining the efficiency of the division method with the low memory usage of an iterative implementation. It uses a loop to repeatedly apply the logic of the Euclidean algorithm, accumulating the operation count at each step without the overhead of function calls.
**Time:** O(log(min(num1, num2))) - The number of iterations in the loop is logarithmic with respect to the smaller of the two numbers, which is the same as the Euclidean algorithm. · **Space:** O(1) - The algorithm uses a fixed number of variables, resulting in constant space usage regardless of the input size.
**Pros:** Optimal time complexity, making it very fast for all valid inputs.; Optimal O(1) space complexity, as it avoids recursion.; Most robust solution, free from stack overflow risks.
**Cons:** The code might be slightly more verbose than the recursive version due to the explicit loop and swap logic.
### Explanation
This method is the iterative counterpart to the recursive solution. It avoids the call stack overhead, making it the most efficient in terms of both time and space. We use a loop and in each iteration, we perform one step of the Euclidean algorithm: add the quotient `num1 / num2` to our count, and then update `num1` to `num1 % num2`. We also make sure `num1` is always the larger of the two numbers before the division to keep the logic consistent.

```java
class Solution {
    public int countOperations(int num1, int num2) {
        int operations = 0;
        while (num1 > 0 && num2 > 0) {
            // Ensure num1 is the larger number
            if (num1 < num2) {
                int temp = num1;
                num1 = num2;
                num2 = temp;
            }
            int quotient = num1 / num2;
            operations += quotient;
            num1 %= num2;
        }
        return operations;
    }
}
```
### Algorithm
- Initialize a counter `operations` to 0.
- Handle the edge case where one of the numbers is already 0 by returning 0.
- Use a `while` loop that continues as long as both `num1` and `num2` are positive.
- Inside the loop, ensure `num1` is always the larger number by swapping them if `num1 < num2`.
- Calculate the quotient: `q = num1 / num2`.
- Add `q` to the `operations` count.
- Update `num1` to be the remainder: `num1 = num1 % num2`.
- The loop terminates when the remainder (`num1`) becomes 0.
- Return the total `operations`.

# Solutions
### Java

```java
class Solution {
public
  int countOperations(int num1, int num2) {
    int ans = 0;
    while (num1 != 0 && num2 != 0) {
      if (num1 >= num2) {
        num1 -= num2;
      } else {
        num2 -= num1;
      }
      ++ans;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} num1 * @param {number} num2 * @return {number} */ var countOperations =
  function (num1, num2) {
    let ans = 0;
    for (; num1 && num2; ++ans) {
      if (num1 >= num2) {
        num1 -= num2;
      } else {
        num2 -= num1;
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int countOperations(int num1, int num2) {
    int ans = 0;
    while (num1 && num2) {
      if (num1 > num2)
        swap(num1, num2);
      num2 -= num1;
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countOperations(self, num1: int, num2: int) -> int: ans = 0 while num1 and num2: if num1 >= num2: num1, num2 = num2, num1 num2 -= num1 ans += 1 return ans

```