Count Operations to Obtain Zero - Solution & Explanation
Problem Statement
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 = 5andnum2 = 4, subtractnum2fromnum1, thus obtainingnum1 = 1andnum2 = 4. However, ifnum1 = 4andnum2 = 5, after one operation,num1 = 4andnum2 = 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
Approach Overview
Problem Overview: You are given two integers num1 and num2. In one operation, subtract the smaller number from the larger one. Repeat until either value becomes zero. The task is to return the total number of operations performed.
Approach 1: Iterative Subtraction (Simulation) (Time: O(max(num1,num2)), Space: O(1))
This approach directly simulates the process described in the problem. While both numbers are non‑zero, compare them and subtract the smaller value from the larger one. After each subtraction, increment the operation counter. The loop stops when one of the values reaches zero.
The logic is straightforward: use a while loop and perform conditional subtraction (num1 -= num2 or num2 -= num1). This mirrors the problem statement exactly and is easy to reason about. The downside is performance when the numbers are very different in size. If num1 is much larger than num2, the loop may run many times because the subtraction happens one step at a time. This solution fits naturally under simulation since it models the operations exactly as defined.
Approach 2: Using Modulus Operation (Optimized Euclidean Idea) (Time: O(log(min(num1,num2))), Space: O(1))
Instead of subtracting the smaller value repeatedly, you can count how many times the subtraction would occur using division. If num1 > num2, then num1 -= num2 would happen num1 / num2 times before num1 becomes smaller than num2. Add that quotient to the operation count and replace num1 with num1 % num2.
This mirrors the logic behind the Euclidean algorithm used to compute the greatest common divisor. Each iteration reduces the larger number dramatically instead of step‑by‑step subtraction. The algorithm repeatedly swaps roles between the two numbers until one becomes zero. The result is significantly fewer iterations, giving logarithmic time complexity.
This technique relies on basic number properties from math and still behaves like a compressed form of simulation. In practice, it is the most efficient and elegant solution.
Recommended for interviews: Start by explaining the iterative subtraction simulation because it directly matches the problem statement and demonstrates clear reasoning. Then optimize it using the modulus observation. Interviewers typically expect the Euclidean-style optimization since it reduces the complexity from potentially linear operations to logarithmic time while keeping constant space.
Approach 1: Iterative Subtraction Approach
This approach is straightforward and simulates the process described in the problem. We repeatedly subtract the smaller number from the larger one until one of them becomes zero. This is similar to the Euclidean algorithm for computing the GCD, except that instead of computing a remainder, we're just performing subtraction until one number reaches zero.
The C solution uses a simple while loop to perform the subtraction. If num1 is greater than or equal to num2, we subtract num2 from num1, otherwise, we subtract num1 from num2. The count variable keeps track of the number of operations performed.
Complexity
Time Complexity: O(max(num1, num2)) because in the worst case we perform subtraction operations until one of the numbers becomes zero. Space Complexity: O(1) as no additional data structures are used.
Approach 2: Using Modulus Operation
An optimized solution is based on using modulus to perform the subtraction in a more efficient manner, similar to the Euclidean algorithm for GCD. Instead of subtracting consecutively, we use the modulus operation to reduce the larger number directly, which minimizes the number of operations.
Instead of repeated subtraction, the C solution uses division and modulus together. We add the quotient of the division as the number of operations and use the modulus to find the new reduced value for num1 or num2.
Complexity
Time Complexity: O(log(min(num1, num2))) similar to the GCD algorithm due to algorithm efficiency. Space Complexity: O(1).
Approach 3: Simulation
We can directly simulate this process by repeatedly performing the following operations:
- If
num1 \ge num2, thennum1 = num1 - num2; - Otherwise,
num2 = num2 - num1. - Each time an operation is performed, increment the operation count by one.
When either num1 or num2 becomes 0, stop the loop and return the operation count.
The time complexity is O(m), where m is the maximum of num1 and num2. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: Default Approach
Code
Python
Approach 5: Mathematics
Following the simulation process in Solution 1, we notice that if num1 is much larger than num2, each operation will only reduce the value of num1 slightly, leading to an excessive number of operations. We can optimize this process by directly adding the quotient of num1 divided by num2 to the answer in each operation, then taking the remainder of num1 divided by num2. This reduces the number of operations.
The time complexity is O(log m), where m is the maximum of num1 and num2. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Subtraction Approach | Time Complexity: O(max(num1, num2)) because in the worst case we perform subtraction operations until one of the numbers becomes zero. Space Complexity: O(1) as no additional data structures are used. |
| Using Modulus Operation | Time Complexity: O(log(min(num1, num2))) similar to the GCD algorithm due to algorithm efficiency. Space Complexity: O(1). |
| Simulation | — |
| Default Approach | — |
| Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Subtraction (Simulation) | O(max(num1, num2)) | O(1) | Best for understanding the problem mechanics or implementing a direct simulation |
| Modulus / Euclidean Optimization | O(log(min(num1, num2))) | O(1) | Preferred for large numbers and optimal interview solutions |
Video Solution
Count Operations to Obtain Zero - Leetcode 2169 - Python • NeetCodeIO • 3,157 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Operations to Obtain Zero easy or hard?
Count Operations to Obtain Zero Python/Java solution
How to solve Count Operations to Obtain Zero in O(log n)?
What is the best approach for Count Operations to Obtain Zero?
Is Count Operations to Obtain Zero asked at Google/Amazon/Meta?
What data structure is used in Count Operations to Obtain Zero?
What is the time complexity of Count Operations to Obtain Zero?
Ready to solve this problem?
Practice Count Operations to Obtain Zero with our built-in code editor and test cases.
Practice on FleetCode