Count Operations to Obtain Zero

Difficulty: Easy | Acceptance: 79.80% | Paid: No Topics: Math, Simulation

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.

Return the number of operations required to make either num1 = 0 or num2 = 0.

• Examples
• Constraints
• Simulation
• Optimized Simulation (Euclidean Algorithm)

Examples

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 and get num1 = 2 - 1 = 1, num2 = 1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1 and get num1 = 1 - 1 = 0, num2 = 1.

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, num2 = 10.

Constraints

0 <= num1, num2 <= 10⁵

Simulation

Intuition Directly implement the operation described in the problem statement. Loop until one of the numbers becomes zero, subtracting the smaller value from the larger one in each step and incrementing a counter.

Steps

• Initialize a counter ops to 0.
• Loop while num1 is greater than 0 and num2 is greater than 0.
• Inside the loop, check if num1 is greater than or equal to num2.
• If yes, subtract num2 from num1. Otherwise, subtract num1 from num2.
• Increment the ops counter.
• Return ops once the loop terminates.

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

Complexity

• Time: O(max(num1, num2)) - In the worst case (e.g., num1=1, num2=10⁵), we perform roughly max(num1, num2) subtractions.
• Space: O(1) - We only use a few variables for storage.
• Notes: This approach is simple but can be slow for large numbers with large differences.

Optimized Simulation (Euclidean Algorithm)

Intuition Instead of subtracting the smaller number from the larger number one by one, we can use division to determine how many times we can subtract the smaller number at once. This is similar to the logic behind the Euclidean algorithm for finding the Greatest Common Divisor (GCD).

Steps

• Initialize a counter ops to 0.
• Loop while num1 is greater than 0 and num2 is greater than 0.
• If num1 is greater than or equal to num2:
  • Add num1 / num2 (integer division) to ops.
  • Update num1 to be num1 % num2.
• Else:
  • Add num2 / num1 (integer division) to ops.
  • Update num2 to be num2 % num1.
• Return ops.

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

Complexity

• Time: O(log(min(num1, num2))) - The number of steps is proportional to the number of steps in the Euclidean algorithm.
• Space: O(1) - Constant space is used.
• Notes: This is the most efficient approach, significantly reducing the number of iterations for large inputs.