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.
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; }}Video 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.