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.
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 <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(min(num1, num2))) similar to the GCD algorithm due to algorithm efficiency. Space Complexity: O(1).
| 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). |
Minimum Operations to Reduce X to Zero - Leetcode 1658 - Python • NeetCodeIO • 16,975 views views
Watch 9 more video solutions →Practice Count Operations to Obtain Zero with our built-in code editor and test cases.
Practice on FleetCode