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.

• For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus new values would be num1 = 1 and num2 = 4. If num1 = 4 and num2 = 5, subtract num1 from num2, thus new values would be num1 = 4 and num2 = 1.

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

Clarifying Questions

1. What happens if both num1 and num2 are zero initially?
   • If both values are zero, then the result should be zero operations.
2. Are the inputs always valid integers?
   • Yes, the problem guarantees that num1 and num2 are non-negative integers.
3. Can both num1 and num2 be zero?
   • Yes, if both are zero, zero operations are needed.

Strategy

1. Initialize a counter operations to zero to keep track of the number of operations.
2. Use a loop to perform the operations until either num1 or num2 becomes zero:
   • If num1 >= num2, subtract num2 from num1.
   • Otherwise, subtract num1 from num2.
   • Increment the operations counter after each operation.
3. Return the operations counter.

Code

public class Solution {
    public 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;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countOperations(5, 4)); // Output: 5
        System.out.println(solution.countOperations(10, 10)); // Output: 1
        System.out.println(solution.countOperations(0, 5)); // Output: 1
        System.out.println(solution.countOperations(0, 0)); // Output: 0
    }
}

Time Complexity

The time complexity for this solution can be analyzed as follows:

• Each operation reduces the value of num1 or num2 by at least one.
• The worst-case scenario would be subtracting 1 repetitively from num1 or num2, which would take a maximum of max(num1, num2) operations.

Thus, the time complexity is O(max(num1, num2)).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?