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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Operations to Obtain Zero

Number: 2288

Difficulty: Easy

Paid? No

Companies: PayU

Problem Description

Given two non-negative integers num1 and num2, we want to count the number of operations required to make either num1 or num2 equal to zero. In each operation, if num1 is greater than or equal to num2, subtract num2 from num1; otherwise subtract num1 from num2.

Key Insights

  • The process naturally terminates when either number becomes zero.
  • When both numbers are equal, one operation will zero-out one of them.
  • Instead of subtracting repeatedly one by one, we can optimize by using division (i.e., use modulo operations) to perform multiple subtractions in one step.
  • The algorithm simulates a Euclidean-like approach and uses the modulo operation to reduce the numbers quickly.

Space and Time Complexity

Time Complexity: O(log(max(num1, num2))) in the average/optimized case, since each step reduces the numbers significantly. In a worst-case scenario with minimal reductions, it behaves linearly. Space Complexity: O(1) as only a few variables are used.

Solution

We use a simulation that closely mirrors the Euclidean algorithm for computing the greatest common divisor (GCD). In each step:

  • If either num1 or num2 is zero, we are done.
  • If num1 is greater than or equal to num2, we compute quotient = num1 // num2 and update num1 = num1 % num2, and vice versa.
  • We add the quotient to our count of operations. This optimization reduces the number of iterations by performing multiple subtractions in one go.

Code Solutions

# Python solution for Count Operations to Obtain Zero

def countOperations(num1, num2):
    # Initialize counter for operations
    operations = 0
    while num1 and num2:
        # If num1 is greater or equal, subtract num2 from num1
        if num1 >= num2:
            # Count how many times num2 fits in num1 (simulate repeated subtraction)
            operations += num1 // num2
            num1 = num1 % num2  # Update num1 to the remainder
        else:
            # Count how many times num1 fits in num2 (simulate repeated subtraction)
            operations += num2 // num1
            num2 = num2 % num1  # Update num2 to the remainder
    return operations

# Example usage:
# print(countOperations(2, 3))
← Back to All Questions