algoadvance

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 or num2 equal to 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3 -> num1 = 2, num2 = 3 - 2 = 1
- Operation 2: num1 = 2, num2 = 1 -> num1 = 2 - 1 = 1, num2 = 1
- Operation 3: num1 = 1, num2 = 1 -> num1 = 1 - 1 = 0, num2 = 1

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10 -> num1 = 10 - 10 = 0, num2 = 10

Constraints:

• 0 <= num1, num2 <= 10^5

Clarifying Questions

1. Should the function return the count of operations only once either num1 or num2 becomes zero?
   • Yes, as stated in the problem.
2. Is it guaranteed that the integers provided will always be non-negative?
   • Yes, as per the problem constraints.

Strategy

1. Initialize a counter to keep track of the number of operations.
2. Use a loop to perform the described operations until either num1 or num2 becomes zero.
3. If num1 >= num2, subtract num2 from num1, otherwise subtract num1 from num2.
4. Increment the counter for each operation performed.
5. Return the counter when the loop ends.

Code

Here’s the implementation of the solution:

def countOperations(num1: int, num2: int) -> int:
    count = 0
    
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
        count += 1
        
    return count

Time Complexity

• Time Complexity: O(min(num1, num2)) - In the worst case, we may subtract 1 from the smaller of either num1 or num2 at each step, leading to min(num1, num2) steps.
• Space Complexity: O(1) - As we use only a constant amount of extra space for the integer variables count, num1, and num2.

In most scenarios, if the number differences are large enough, the number of operations could be significantly less than the minimum value of num1 and num2, closer to log(min(num1, num2)).

Try our interview co-pilot at AlgoAdvance.com

• 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?