Count Operations to Obtain Zero

EASY

Description

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.

For example, if 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 <= 10⁵

Approaches

Checkout 3 different approaches to solve Count Operations to Obtain Zero. Click on different approaches to view the approach and algorithm in detail.

Simple Simulation using Subtraction

This is a straightforward approach that directly simulates the process described in the problem. We repeatedly subtract the smaller number from the larger number in a loop and count how many times we perform this operation until one of the numbers becomes zero.

Algorithm

Initialize a counter operations to 0.
Use a while loop that continues as long as both num1 and num2 are greater than 0.
Inside the loop, compare num1 and num2.
If num1 >= num2, subtract num2 from num1.
Otherwise, subtract num1 from num2.
Increment the operations counter in each iteration.
The loop terminates when one of the numbers becomes 0. Return the operations count.

The algorithm maintains a loop that runs as long as neither of the two numbers is zero. In each step of the loop, it checks which number is larger and performs the subtraction accordingly. A counter is incremented for each subtraction. This process is identical to the Euclidean algorithm using subtraction.

class Solution {
    public int countOperations(int num1, int num2) {
        int operations = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) {
                num1 = num1 - num2;
            } else {
                num2 = num2 - num1;
            }
            operations++;
        }
        return operations;
    }
}

Complexity Analysis

Time Complexity: O(max(num1, num2)) - In the worst-case scenario (e.g., one number is 1), the number of operations is proportional to the larger number. Let N = max(num1, num2) and M = min(num1, num2), the complexity is roughly O(N/M * M) in some cases, but a simpler upper bound is O(N).Space Complexity: O(1) - We only use a few variables to store the current numbers and the operation count, so the space required is constant.

Pros and Cons

Pros:

Very simple to understand and implement.
Directly translates the problem description into code.

Cons:

This approach can be very slow if one number is much larger than the other. For instance, if num1 = 100000 and num2 = 1, it would take 100000 operations.
May result in a 'Time Limit Exceeded' (TLE) error for larger inputs within the given constraints.

Code Solutions

Checking out 4 solutions in different languages for Count Operations to Obtain Zero. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Count Operations to Obtain Zero

Patterns:

Math

Companies:

Accenture |Capital One |PayU |