Count Operations to Obtain Zero
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
operationsto 0. - Use a
whileloop that continues as long as bothnum1andnum2are greater than 0. - Inside the loop, compare
num1andnum2. - If
num1 >= num2, subtractnum2fromnum1. - Otherwise, subtract
num1fromnum2. - Increment the
operationscounter in each iteration. - The loop terminates when one of the numbers becomes 0. Return the
operationscount.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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 = 100000andnum2 = 1, it would take 100000 operations.May result in a 'Time Limit Exceeded' (TLE) error for larger inputs within the given constraints.
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.
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
num1andnum2as 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
num1is the larger number (swapping if necessary). - We calculate how many times
num2can be subtracted fromnum1in one go, which isquotient = num1 / num2. - The new state of the numbers becomes
(num2, num1 % num2). - The result is the sum of the
quotientand the result of the recursive call with the new numbers:quotient + countOperations(num2, num1 % num2).
Walkthrough
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.
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); } }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a counter
operationsto 0. - Handle the edge case where one of the numbers is already 0 by returning 0.
- Use a
whileloop that continues as long as bothnum1andnum2are positive. - Inside the loop, ensure
num1is always the larger number by swapping them ifnum1 < num2. - Calculate the quotient:
q = num1 / num2. - Add
qto theoperationscount. - Update
num1to be the remainder:num1 = num1 % num2. - The loop terminates when the remainder (
num1) becomes 0. - Return the total
operations.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}/** * @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; };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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.