We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Operations to Obtain Zero

Difficulty: Easy

Problem 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. Return the number of operations required to make either num1 = 0 or num2 = 0.

Key Insights

  • The operations are based on comparing num1 and num2.
  • Each operation reduces one of the numbers, leading to a possible optimization.
  • The problem can be viewed as repeatedly reducing the larger number by the smaller number.
  • If both numbers are equal, only one operation is needed to make one of them zero.

Space and Time Complexity

Time Complexity: O(max(num1, num2))
Space Complexity: O(1)

Solution

The approach involves repeatedly comparing the two numbers and performing subtraction based on their values. Instead of simulating each operation, we can optimize by directly calculating how many times we can subtract the smaller number from the larger one. This can be done using integer division, which allows us to count operations more efficiently. The algorithm continues until at least one of the numbers reaches zero.

Code Solutions

def countOperations(num1: int, num2: int) -> int:
    operations = 0
    while num1 > 0 and num2 > 0:
        if num1 >= num2:
            operations += num1 // num2  # Count how many times num2 can be subtracted from num1
            num1 = num1 % num2  # Update num1 to the remainder
        else:
            operations += num2 // num1  # Count how many times num1 can be subtracted from num2
            num2 = num2 % num1  # Update num2 to the remainder
    return operations
← Back to All Questions