Problem statement

You are given two non-negative integers num1 and num2.

Repeat this operation until one of them becomes 0: if num1 >= num2, subtract num2 from num1; otherwise subtract num1 from num2.

Return the number of operations performed.

Example 1

Input: num1 = 2, num2 = 3
Output: 3
Explanation: (2,3) → (2,1) → (1,1) → (1,0).

Example 2

Input: num1 = 10, num2 = 10
Output: 1
Explanation: One subtraction makes both sides zero.

Example 3

Input: num1 = 0, num2 = 5
Output: 0
Explanation: One is already zero, so no operation runs.

Constraints

• 0 <= num1, num2 <= 100000

Hints for Count Operations to Obtain Zero

1. Hint 1

   Simulating one subtraction at a time is fine for small inputs but is slow when one number dwarfs the other.

2. Hint 2

   Subtracting b from a repeatedly is exactly integer division.

3. Hint 3

   That makes the whole loop the Euclidean algorithm, counting quotients instead of discarding them.

How to solve Count Operations to Obtain Zero

Repeatedly subtracting the smaller value from the larger is the subtractive form of Euclid's algorithm. Replacing each run of identical subtractions with one division collapses the operation count into a sum of quotients.

Approach

1. While neither value is zero, let the larger be a and the smaller b.
2. Add a / b (integer division) to the operation count — that is how many subtractions the naive loop would perform in a row.
3. Replace a with a % b and continue.
4. Return the accumulated count.

Why it works

Subtracting b from a exactly floor(a/b) times leaves a % b, which is by definition smaller than b, so the roles swap on the next iteration. The quotient sum therefore equals the number of individual subtractions.

Complexity

• Time — O(log(min(num1, num2)))
• Space — O(1)

Pitfalls

• The naive one-subtraction-at-a-time loop takes 100,000 steps for (100000, 1).
• Equal values must count as one operation, which the a >= b branch handles by making a % b == 0.
• A zero input must return 0, not loop forever — the guard is on the loop condition.

Reference solution

Python

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

Java

public static int countOperations(int num1, int num2) {
    int ops = 0;
    while (num1 != 0 && num2 != 0) {
        if (num1 >= num2) {
            ops += num1 / num2;
            num1 %= num2;
        } else {
            ops += num2 / num1;
            num2 %= num1;
        }
    }
    return ops;
}

C++

int countOperations(int num1, int num2) {
    int ops = 0;
    while (num1 != 0 && num2 != 0) {
        if (num1 >= num2) {
            ops += num1 / num2;
            num1 %= num2;
        } else {
            ops += num2 / num1;
            num2 %= num1;
        }
    }
    return ops;
}

JavaScript

var countOperations = function(num1, num2) {
    let ops = 0;
    while (num1 !== 0 && num2 !== 0) {
        if (num1 >= num2) {
            ops += Math.floor(num1 / num2);
            num1 = num1 % num2;
        } else {
            ops += Math.floor(num2 / num1);
            num2 = num2 % num1;
        }
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy