#2169

Easy

LeetCode Problem Workspace

Count Operations to Obtain Zero

Simulate operations on two integers until one becomes zero, counting how many steps it takes to achieve the result.

Problem Statement

Given two non-negative integers, num1 and num2, you need to repeatedly subtract the smaller number from the larger number. The operation continues until either num1 or num2 is reduced to zero.

Return the total number of operations needed to make one of the integers equal to zero. If num1 >= num2, subtract num2 from num1; otherwise, subtract num1 from num2.

Examples

Example 1

Input: num1 = 2, num2 = 3

Output: 3

Operation 1: num1 = 2, num2 = 3. 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

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

Solution Approach

Simulate the Process

Start by comparing num1 and num2. If num1 >= num2, subtract num2 from num1; otherwise, subtract num1 from num2. Count each operation and continue until either num1 or num2 becomes zero.

Efficiency Considerations

While simulating the process step-by-step is intuitive, consider optimizing the operations by reducing the problem to a mathematical model that accelerates the process using division, especially when both numbers are large.

Edge Cases

Handle cases where num1 or num2 is already zero before performing any operations. This will immediately terminate the process with no operations needed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can vary depending on the approach, but a direct simulation results in linear time proportional to the values of num1 and num2. Optimized approaches might reduce this to logarithmic time in some cases, especially when division is used to jump over multiple steps.

What Interviewers Usually Probe

Tests understanding of basic simulation techniques.
Evaluates efficiency considerations in problem-solving.
Looks for correct handling of edge cases and optimized solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to consider edge cases, such as when either num1 or num2 is already zero.
Overcomplicating the solution when a simple simulation is sufficient.
Not optimizing the process for larger values of num1 and num2.

Follow-up variants

Consider handling larger inputs efficiently using mathematical shortcuts.
Modify the problem to count operations to reach a specific value other than zero.
Introduce a constraint that only allows subtraction in certain conditions, altering the simulation.

FAQ

What is the core approach to solving the Count Operations to Obtain Zero problem?

The core approach is simulating the process of subtracting the smaller number from the larger number, repeating this until either num1 or num2 reaches zero.

Can the Count Operations to Obtain Zero problem be optimized?

Yes, it can be optimized by reducing the number of operations using division, especially for larger values of num1 and num2.

What should I do if one of the numbers is already zero?

If either num1 or num2 is zero at the start, no operations are needed, and you can return zero immediately.

What is the time complexity of the Count Operations to Obtain Zero solution?

The time complexity depends on the approach used, with a direct simulation being linear in time, while optimized methods can reduce this to logarithmic time.

What other variations of the problem can be explored?

Variants may include applying different constraints or counting operations to reach a value other than zero.

terminal

Solution

Solution 1: Simulation

We can directly simulate this process by repeatedly performing the following operations:

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                num1 -= num2
            else:
                num2 -= num1
            ans += 1
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                num1 -= num2
            else:
                num2 -= num1
            ans += 1
        return ans

Solution 2: Mathematics

Following the simulation process in Solution 1, we notice that if $\textit{num1}$ is much larger than $\textit{num2}$, each operation will only reduce the value of $\textit{num1}$ slightly, leading to an excessive number of operations. We can optimize this process by directly adding the quotient of $\textit{num1}$ divided by $\textit{num2}$ to the answer in each operation, then taking the remainder of $\textit{num1}$ divided by $\textit{num2}$. This reduces the number of operations.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                num1 -= num2
            else:
                num2 -= num1
            ans += 1
        return ans

Continue Practicing

#2177 find three consecutive integers that sum to a given number #2180 count integers with even digit sum #2221 find triangular sum of an array