Problem Description

You are given two non-negative integers num1 and num2.

The task is to perform a series of operations until one of the numbers becomes 0. In each operation:

• If num1 >= num2, subtract num2 from num1
• Otherwise, subtract num1 from num2

For example:

• Starting with num1 = 5 and num2 = 4:
  • Since 5 >= 4, we perform num1 = 5 - 4 = 1, resulting in num1 = 1 and num2 = 4
• Starting with num1 = 4 and num2 = 5:
  • Since 4 < 5, we perform num2 = 5 - 4 = 1, resulting in num1 = 4 and num2 = 1

The goal is to return the total number of operations required to make either num1 = 0 or num2 = 0.

This process simulates repeatedly subtracting the smaller number from the larger number until one of them reaches zero, counting each subtraction as one operation.

Intuition

The problem is essentially asking us to simulate a process that resembles finding the greatest common divisor (GCD) using the subtraction method, but we need to count the steps rather than find the GCD itself.

The key observation is that we're always subtracting the smaller number from the larger one. This process continues until one number becomes 0. At each step, we're reducing the total sum of the two numbers, guaranteeing that the process will eventually terminate.

Let's trace through an example to understand the pattern:

• If we have num1 = 7 and num2 = 3:
  • Step 1: 7 - 3 = 4, so num1 = 4, num2 = 3
  • Step 2: 4 - 3 = 1, so num1 = 1, num2 = 3
  • Step 3: 3 - 1 = 2, so num1 = 1, num2 = 2
  • Step 4: 2 - 1 = 1, so num1 = 1, num2 = 1
  • Step 5: 1 - 1 = 0, so num1 = 0, num2 = 1
  • Total operations: 5

The straightforward approach is to directly simulate what the problem describes: keep track of both numbers, perform the subtraction based on which is larger, and count each operation. Since we're always making progress (reducing at least one number), and the numbers are non-negative, we're guaranteed to reach 0 eventually.

The simulation approach works well here because:

1. The operation rules are clearly defined
2. We have a clear termination condition (when either number becomes 0)
3. Each operation brings us closer to the termination condition

Learn more about Math patterns.

Solution Approach

The solution implements a direct simulation approach using a simple while loop. Here's how the implementation works:

1. Initialize a counter: We start with ans = 0 to keep track of the number of operations performed.

2. Loop condition: We use while num1 and num2 which continues as long as both numbers are non-zero. The loop terminates when either num1 or num2 becomes 0.

3. Perform the operation: Inside the loop, we check which number is larger:

   • If num1 >= num2, we subtract num2 from num1: num1 = num1 - num2
   • Otherwise, we subtract num1 from num2: num2 = num2 - num1

4. Count the operation: After each subtraction, we increment the counter: ans += 1

5. Return the result: Once the loop exits (when one number becomes 0), we return the total count ans.

The algorithm follows these steps:

ans = 0
while num1 and num2:
    if num1 >= num2:
        num1 -= num2
    else:
        num2 -= num1
    ans += 1
return ans

Time Complexity: The time complexity depends on the values of num1 and num2. In the worst case, if one number is much larger than the other, we might need to perform many subtractions. The complexity is proportional to the larger number divided by the smaller number.

Space Complexity: O(1) as we only use a constant amount of extra space for the counter variable.

The beauty of this solution lies in its simplicity - it directly translates the problem statement into code without any complex transformations or optimizations.

Example Walkthrough

Let's walk through the solution with num1 = 10 and num2 = 3:

Initial state: num1 = 10, num2 = 3, ans = 0

Operation 1: Since 10 >= 3, we subtract: num1 = 10 - 3 = 7

• Result: num1 = 7, num2 = 3, ans = 1

Operation 2: Since 7 >= 3, we subtract: num1 = 7 - 3 = 4

• Result: num1 = 4, num2 = 3, ans = 2

Operation 3: Since 4 >= 3, we subtract: num1 = 4 - 3 = 1

• Result: num1 = 1, num2 = 3, ans = 3

Operation 4: Since 1 < 3, we subtract: num2 = 3 - 1 = 2

• Result: num1 = 1, num2 = 2, ans = 4

Operation 5: Since 1 < 2, we subtract: num2 = 2 - 1 = 1

• Result: num1 = 1, num2 = 1, ans = 5

Operation 6: Since 1 >= 1, we subtract: num1 = 1 - 1 = 0

• Result: num1 = 0, num2 = 1, ans = 6

Termination: Since num1 = 0, the while loop exits.

Return: The function returns ans = 6

The process required 6 operations to reduce one of the numbers to 0. Notice how we always subtract the smaller value from the larger one, gradually reducing the numbers until one reaches zero.

Solution Implementation

Time and Space Complexity

The time complexity is O(max(num1, num2)) in the worst case. This occurs when one number is much larger than the other, or when the numbers are consecutive (like num1 = n and num2 = 1). In such cases, the algorithm essentially performs repeated subtractions similar to the Euclidean algorithm for finding GCD. For example, with num1 = 100 and num2 = 1, the loop will execute 100 times, subtracting 1 from 100 repeatedly until num1 becomes 0.

More precisely, the number of operations is bounded by max(num1, num2) / min(num1, num2) when min(num1, num2) > 0. The algorithm behaves similarly to the subtraction-based GCD algorithm, where each iteration reduces the larger number by the smaller one.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. It modifies the input parameters num1 and num2 in-place and only maintains one additional variable ans to count the operations. No additional data structures or recursive calls are used that would increase the space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficiency with Large Number Differences

The Pitfall: When one number is significantly larger than the other (e.g., num1 = 1000000 and num2 = 1), the naive simulation approach performs an excessive number of operations. Each iteration only subtracts the smaller value once, leading to potentially millions of iterations.

Example Scenario:

• With num1 = 1000 and num2 = 3, the algorithm would perform 333 subtractions one by one
• This becomes extremely slow for larger values like num1 = 10^9 and num2 = 1

Solution - Optimization Using Division: Instead of subtracting repeatedly, we can calculate how many times the smaller number fits into the larger number using integer division. This reduces multiple operations into a single calculation:

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        operation_count = 0
      
        while num1 != 0 and num2 != 0:
            if num1 >= num2:
                # Calculate how many times num2 fits into num1
                operations_batch = num1 // num2
                operation_count += operations_batch
                # Update num1 to the remainder
                num1 = num1 % num2
            else:
                # Calculate how many times num1 fits into num2
                operations_batch = num2 // num1
                operation_count += operations_batch
                # Update num2 to the remainder
                num2 = num2 % num1
      
        return operation_count

This optimization transforms the time complexity from O(max(num1, num2)) to O(log(min(num1, num2))), which is essentially the Euclidean algorithm for finding GCD.

2. Not Handling Edge Cases

The Pitfall: Failing to consider when one or both inputs are already zero.

Solution: Add an early return check:

if num1 == 0 or num2 == 0:
    return 0

3. Integer Overflow in Other Languages

The Pitfall: While Python handles arbitrary precision integers automatically, implementing this in languages like C++ or Java might face integer overflow issues during intermediate calculations.

Solution: Use appropriate data types (like long long in C++ or long in Java) and be mindful of the maximum values that can be handled.