Count Operations to Obtain Zero - Video Solutions

Problem Overview: You are given two integers num1 and num2. In one operation, subtract the smaller number from the larger one. Repeat until either value becomes zero. The task is to return the total number of operations performed.

Approach 1: Iterative Subtraction (Simulation) (Time: O(max(num1,num2)), Space: O(1))

This approach directly simulates the process described in the problem. While both numbers are non‑zero, compare them and subtract the smaller value from the larger one. After each subtraction, increment the operation counter. The loop stops when one of the values reaches zero.

The logic is straightforward: use a while loop and perform conditional subtraction (num1 -= num2 or num2 -= num1). This mirrors the problem statement exactly and is easy to reason about. The downside is performance when the numbers are very different in size. If num1 is much larger than num2, the loop may run many times because the subtraction happens one step at a time. This solution fits naturally under simulation since it models the operations exactly as defined.

Approach 2: Using Modulus Operation (Optimized Euclidean Idea) (Time: O(log(min(num1,num2))), Space: O(1))

Instead of subtracting the smaller value repeatedly, you can count how many times the subtraction would occur using division. If num1 > num2, then num1 -= num2 would happen num1 / num2 times before num1 becomes smaller than num2. Add that quotient to the operation count and replace num1 with num1 % num2.

This mirrors the logic behind the Euclidean algorithm used to compute the greatest common divisor. Each iteration reduces the larger number dramatically instead of step‑by‑step subtraction. The algorithm repeatedly swaps roles between the two numbers until one becomes zero. The result is significantly fewer iterations, giving logarithmic time complexity.

This technique relies on basic number properties from math and still behaves like a compressed form of simulation. In practice, it is the most efficient and elegant solution.

Recommended for interviews: Start by explaining the iterative subtraction simulation because it directly matches the problem statement and demonstrates clear reasoning. Then optimize it using the modulus observation. Interviewers typically expect the Euclidean-style optimization since it reduces the complexity from potentially linear operations to logarithmic time while keeping constant space.