Count Operations to Obtain Zero

Easy

Capital One

2 views

Topics:

Greedy AlgorithmsBit Manipulation

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⁵

Count Operations to Obtain Zero

Easy

Capital One

2 views

Topics:

Greedy AlgorithmsBit Manipulation

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⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for `num1` and `num2`? Could they be very large numbers?
Are `num1` and `num2` guaranteed to be non-negative integers, or do I need to handle negative numbers or floating-point values?
If either `num1` or `num2` is initially zero, should the function return 0 immediately?
Is there a risk of integer overflow during the subtraction operations, and should I take that into account?
Are there any specific performance expectations or time complexity constraints for the solution?

Brute Force Solution

Approach

We're trying to figure out the minimum number of steps to make two numbers zero. A brute force approach means we simply keep subtracting the smaller number from the larger number, one step at a time, and count how many subtractions it takes until we reach our goal.

Here's how the algorithm would work step-by-step:

Compare the two numbers.
Subtract the smaller number from the larger number.
Increase our operation count by one.
Check if either number is now zero.
If not, repeat the process starting from comparing the two (potentially) new numbers.
Keep repeating until at least one number is zero.
The final operation count is the answer.

Code Implementation

def count_operations_to_obtain_zero(number1, number2):
    operation_count = 0

    while number1 != 0 and number2 != 0:
        # Determine which number is greater
        if number1 >= number2:
            number1 = number1 - number2

        else:
            number2 = number2 - number1

        operation_count = operation_count + 1

    return operation_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(max(value1, value2)) – The number of operations is driven by how many times we can subtract the smaller number from the larger number until one of them becomes zero. In the worst-case scenario, one number is significantly larger than the other. The while loop continues as long as both numbers are greater than zero. Therefore, the maximum number of iterations and thus the time complexity is proportional to the larger of the two input values.

Space Complexity

O(1) – The provided algorithm operates directly on the input numbers and uses only a single integer variable to keep track of the operation count. It does not create any auxiliary data structures like arrays, lists, or hash maps. Therefore, the memory required by the algorithm remains constant regardless of the input numbers, and the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks to find how many subtractions are needed to make two numbers zero. Instead of directly subtracting one by one, we'll focus on repeatedly subtracting the smaller number from the larger one until one of them becomes zero.

Here's how the algorithm would work step-by-step:

Find out which of the two numbers is bigger and which is smaller.
Subtract the smaller number from the bigger number and increase the operation count by one.
Repeat this process of finding the bigger/smaller and subtracting until one of the numbers reaches zero.
The total operation count is the answer you're looking for.

Code Implementation

def count_operations_to_obtain_zero(number1, number2):
    operation_count = 0

    while number1 != 0 and number2 != 0:
        # Determine the larger and smaller number
        if number1 >= number2:

            number1 = number1 - number2
            operation_count += 1

        else:
            # Subtract the larger number from the smaller.

            number2 = number2 - number1
            operation_count += 1

    # Count of subtractions until a number becomes zero.
    return operation_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(max(num1, num2)) – The algorithm repeatedly subtracts the smaller number from the larger number until one of them becomes zero. In the worst-case scenario, one number (say num1) is significantly larger than the other (num2). The number of subtractions will then be proportional to the value of the larger number (num1) before it reaches zero. Hence, the time complexity is directly proportional to the larger of the two input numbers, which can be expressed as O(max(num1, num2)).

Space Complexity

O(1) – The algorithm operates directly on the input numbers (num1 and num2). It only requires a constant amount of extra space to store the operation count, and potentially temporary variables for comparing num1 and num2, none of which depend on the magnitude of the input numbers. Therefore, the space complexity is constant, independent of the input values.

Edge Cases

Case	How to Handle
num1 or num2 is initially zero	The loop condition immediately terminates, and the function correctly returns 0.
num1 and num2 are equal and non-zero	The first operation results in one of the numbers becoming zero, and the function returns 1.
num1 and num2 are very large numbers (close to the maximum integer value)	The iterative subtraction might take a long time, but the integer values are guaranteed to stay within range, so the algorithm eventually terminates.
One number is significantly larger than the other (highly skewed distribution)	The algorithm will perform many subtractions of the smaller number from the larger number, but it remains correct and will eventually terminate.
Both num1 and num2 are 1	The algorithm will perform one subtraction and return 1.
Integer overflow during subtraction (though inputs are non-negative)	Since the inputs are non-negative, and we only perform subtraction where the result is known to be non-negative, integer overflow cannot occur.
num1 and num2 are both very close to 0, like 1 and 2	Algorithm handles small numbers correctly by iterative subtraction.
One number is 0 and the other is large	The loop immediately terminates returning 0 as the result.