LeetCode 2169 - Count Operations to Obtain Zero

LeetCode Problem 2169

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

The problem asks us to count the number of operations required to reduce either of two non-negative integers num1 or num2 to zero. An operation is defined as subtracting the smaller number from the larger one (or subtracting either if they are equal). We continue performing operations until at least one of the numbers becomes zero.

The input consists of two integers, both constrained between 0 and 105, inclusive. The output is a single integer representing the total number of operations required.

Important observations include handling cases where one of the numbers is initially zero, which means zero operations are needed, and when the numbers are equal, which will immediately reduce one to zero in a single operation.

Edge cases to consider are inputs where either number is zero, inputs where the numbers are equal, and inputs where one number is much larger than the other.

Approaches

The most straightforward approach is brute force simulation. Here, we repeatedly compare num1 and num2, perform the subtraction operation according to the rules, and increment a counter until either number becomes zero. This approach is simple and correct but can be slow if the numbers are large, as each subtraction only reduces one number by a small amount, potentially requiring many iterations.

The optimal approach leverages the observation that repeatedly subtracting the smaller number from the larger is equivalent to performing integer division. Specifically, for two numbers a and b where a >= b, the number of subtractions needed to reduce a below b is a // b. After this step, we only need to continue with a % b and b. Repeating this mimics the Euclidean algorithm used to compute the greatest common divisor (GCD). This significantly reduces the number of iterations because each step reduces the larger number by a multiple of the smaller number.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(max(num1, num2))	O(1)	Simulate operations one by one
Optimal	O(log(max(num1, num2)))	O(1)	Use division and modulo like Euclidean algorithm

Algorithm Walkthrough

1. Initialize a counter operations to zero. This will keep track of the number of operations performed.
2. Loop while both num1 and num2 are non-zero.
3. At each iteration, identify the larger and smaller number.
4. Add the quotient of the larger number divided by the smaller number (num1 // num2 or num2 // num1) to operations. This counts how many times the subtraction could occur at once.
5. Update the larger number to its remainder after division (num1 % num2 or num2 % num1), which mimics performing multiple subtraction operations in a single step.
6. Continue until either number becomes zero.
7. Return operations.

Why it works: The algorithm works because repeatedly subtracting the smaller number from the larger is equivalent to performing a division and taking the remainder. The number of subtractions needed is exactly the quotient, and the remainder becomes the new larger number in subsequent iterations. This reduces the number of steps exponentially compared to the brute force approach, while maintaining correctness.

Python Solution

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

In this Python implementation, we maintain a running total of operations. We use a while loop to continue processing until one number reaches zero. Within the loop, we always subtract the smaller number from the larger, counting multiple subtractions at once using integer division. The modulo operation updates the larger number efficiently. This approach handles edge cases like one number being zero or both numbers being equal.

Go Solution

func countOperations(num1 int, num2 int) int {
    operations := 0
    for num1 != 0 && num2 != 0 {
        if num1 >= num2 {
            operations += num1 / num2
            num1 %= num2
        } else {
            operations += num2 / num1
            num2 %= num1
        }
    }
    return operations
}

The Go implementation mirrors the Python approach. Integer division / and modulo % are used to count multiple operations at once and update the larger number. Edge cases such as zeros and equal numbers are handled identically.

Worked Examples

Example 1: num1 = 2, num2 = 3

Step	num1	num2	Operation Count
Initial	2	3	0
1	2	1 (3 % 2)	1 (3 // 2)
2	1 (2 % 1)	1	2 (2 // 1)
3	0 (1 % 1)	1	3 (1 // 1)

Output: 3

Example 2: num1 = 10, num2 = 10

Step	num1	num2	Operation Count
Initial	10	10	0
1	0 (10 % 10)	10	1 (10 // 10)

Output: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(max(num1, num2)))	Each iteration reduces the larger number by modulo, similar to Euclidean GCD algorithm, leading to logarithmic steps.
Space	O(1)	Only a fixed number of integer variables are used.

The Euclidean-like division reduces the numbers quickly, ensuring the algorithm scales efficiently even for the upper bound of 105.

Test Cases

# Provided examples
assert Solution().countOperations(2, 3) == 3  # small numbers, num1 < num2
assert Solution().countOperations(10, 10) == 1  # equal numbers

# Edge cases
assert Solution().countOperations(0, 5) == 0  # num1 is zero
assert Solution().countOperations(7, 0) == 0  # num2 is zero
assert Solution().countOperations(1, 105) == 105  # large difference
assert Solution().countOperations(105, 1) == 105  # large difference reversed
assert Solution().countOperations(13, 17) == 6  # random small numbers
assert Solution().countOperations(105, 105) == 1  # largest equal numbers

Test	Why
(2, 3)	Tests num1 < num2
(10, 10)	Tests equal numbers
(0, 5)	Tests num1 is zero
(7, 0)	Tests num2 is zero
(1, 105)	Tests large difference, small num1
(105, 1)	Tests large difference, small num2
(13, 17)	Random numbers
(105, 105)	Upper bound equal numbers

Edge Cases

The first edge case is when either num1 or num2 is initially zero. The algorithm handles this because the loop condition num1 != 0 and num2 != 0 immediately fails, returning zero operations as expected.

The second edge case occurs when num1 and num2 are equal. In this case, only one operation is needed because num1 - num2 or num2 - num1 immediately reduces one number to zero. Our division-based approach correctly adds 1 to the operation count and terminates.

The third edge case is when one number is significantly larger than the other. A naive implementation might subtract the smaller number one at a time, requiring many iterations. The optimal algorithm efficiently handles this by using integer division to count multiple subtractions in one step, ensuring performance even for the upper limit of 105.