{x}
blog image

Count Operations to Obtain Zero

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

Solution Explanation for LeetCode 2169: Count Operations to Obtain Zero

This problem asks us to find the number of operations needed to reduce either num1 or num2 to zero. In each operation, we subtract the smaller number from the larger number. We can solve this using two approaches: simulation and a mathematical optimization.

Approach 1: Simulation

This approach directly simulates the process described in the problem statement. We repeatedly perform operations until one of the numbers becomes zero.

Algorithm:

  1. Initialize a counter ans to 0.
  2. While both num1 and num2 are greater than 0:
    • If num1 is greater than or equal to num2, subtract num2 from num1.
    • Otherwise, subtract num1 from num2.
    • Increment ans (the operation count) by 1.
  3. Return ans.

Time Complexity: O(max(num1, num2)) - In the worst case, the loop runs until the larger number is reduced to 0. The number of iterations is proportional to the larger of the two input numbers.

Space Complexity: O(1) - We only use a few integer variables.

Code (Python):

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

Approach 2: Mathematical Optimization

The simulation approach can be inefficient for large inputs. We can optimize it using the observation that repeatedly subtracting the smaller number is essentially equivalent to integer division and modulo operations.

Algorithm:

  1. Initialize a counter ans to 0.
  2. While both num1 and num2 are greater than 0:
    • If num1 is greater than or equal to num2:
      • Add num1 // num2 (integer division) to ans.
      • Update num1 to num1 % num2 (modulo operation).
    • Otherwise:
      • Add num2 // num1 to ans.
      • Update num2 to num2 % num1.
  3. Return ans.

Time Complexity: O(log(max(num1, num2))) - The number of iterations is significantly reduced because we're using division instead of repeated subtraction. The number of iterations is approximately proportional to the number of bits in the larger number.

Space Complexity: O(1)

Code (Python):

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                ans += num1 // num2
                num1 %= num2
            else:
                ans += num2 // num1
                num2 %= num1
        return ans

The mathematical optimization provides a much more efficient solution for larger input values. Both approaches are correct, but the second one has a superior time complexity. The provided code examples show the optimized solution in various languages.