algoadvance

Leetcode 2169. Count Operations to Obtain Zero

Problem Statement

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.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Clarifying Questions

  1. What are the constraints on num1 and num2?
    • The problem should define bounds on num1 and num2. Typical constraints are non-negative integers within a practical range, such as 0 ≤ num1, num2 ≤ 10^9.
  2. What if both numbers are already zero?
    • Clarify if this is an input case that needs to be handled. From the problem example, it appears they are non-negative integers, not necessarily positive.
  3. Is there a constraint on the number of operations?
    • Typically, this would not be such a constraint, but understanding usual input sizes helps to optimize the solution.

Strategy

  1. While Loop and Subtraction:
    • Use a while loop to continue operations until either num1 or num2 becomes zero.
    • In each iteration, check whether num1 is greater than or equal to num2. If true, subtract num2 from num1.
    • Otherwise, subtract num1 from num2.
    • Count each operation and return the count when done.
  2. Optimal Approach:
    • Given the nature of the problem, directly simulating the process should be efficient enough. Special consideration for large inputs may be required, but typically, basic subtraction as per requirements within given constraints is effective.

Time Complexity

The time complexity of the approach is O(max(num1, num2)) in the worst case, where the numbers must be repeatedly subtracted. Due to large potential sizes, we should consider the number of steps carefully.

Code

#include <iostream>

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

int main() {
    int num1 = 12;
    int num2 = 15;
    std::cout << "Number of operations: " << countOperations(num1, num2) << std::endl;
    return 0;
}

In this implementation, we use a simple loop to repeatedly perform the given subtraction operations until one of the numbers becomes zero, counting each operation performed. This should meet the problem requirements efficiently within the standard constraints of competitive programming.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI