Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Repeatedly subtracting the smaller positive number from the larger can be batched: the quotient counts how many subtractions occur before the remainder becomes smaller. This is the Euclidean algorithm with the quotients accumulated as operation counts.

Approach

While both values are nonzero, add num1 // num2 to the answer, replace num1 with its remainder modulo num2, and swap the two values. If the first value initially is smaller, the quotient is zero and the swap simply puts them in the useful order. Stop when either becomes zero and return the accumulated subtractions. Equal positive values contribute one operation; an initially zero value contributes none.

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        # O(max(num1, num2))
        # res = 0
        # while num1 and num2:
            # if num1 >= num2: num1 -= num2
            # else: num2 -= num1
            # res += 1
        # return res
        # O(log(max(num1, num2)))

        res = 0

        while num1 and num2:
            res += num1 // num2
            num1 %= num2
            num1, num2 = num2, num1

        return res

Complexity analysis

Let V = max(num1, num2). Under the bounded-integer arithmetic model, time is O(log(V + 2)) for quotient/remainder Euclidean iterations and auxiliary space is O(1). An initially zero value returns immediately; the +2 includes V = 0 or 1.