2169. Count Operations to Obtain Zero - Solution

The problem

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.

For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

0 <= num1, num2 <= 10⁵

Approach overview

Problem Overview: You are given two integers num1 and num2. In one operation, subtract the smaller number from the larger one. Repeat until either value becomes zero. The task is to return the total number of operations performed.

Approach 1: Iterative Subtraction (Simulation) (Time: O(max(num1,num2)), Space: O(1))

This approach directly simulates the process described in the problem. While both numbers are non‑zero, compare them and subtract the smaller value from the larger one. After each subtraction, increment the operation counter. The loop stops when one of the values reaches zero.

The logic is straightforward: use a while loop and perform conditional subtraction (num1 -= num2 or num2 -= num1). This mirrors the problem statement exactly and is easy to reason about. The downside is performance when the numbers are very different in size. If num1 is much larger than num2, the loop may run many times because the subtraction happens one step at a time. This solution fits naturally under simulation since it models the operations exactly as defined.

Approach 2: Using Modulus Operation (Optimized Euclidean Idea) (Time: O(log(min(num1,num2))), Space: O(1))

Instead of subtracting the smaller value repeatedly, you can count how many times the subtraction would occur using division. If num1 > num2, then num1 -= num2 would happen num1 / num2 times before num1 becomes smaller than num2. Add that quotient to the operation count and replace num1 with num1 % num2.

This mirrors the logic behind the Euclidean algorithm used to compute the greatest common divisor. Each iteration reduces the larger number dramatically instead of step‑by‑step subtraction. The algorithm repeatedly swaps roles between the two numbers until one becomes zero. The result is significantly fewer iterations, giving logarithmic time complexity.

This technique relies on basic number properties from math and still behaves like a compressed form of simulation. In practice, it is the most efficient and elegant solution.

Recommended for interviews: Start by explaining the iterative subtraction simulation because it directly matches the problem statement and demonstrates clear reasoning. Then optimize it using the modulus observation. Interviewers typically expect the Euclidean-style optimization since it reduces the complexity from potentially linear operations to logarithmic time while keeping constant space.

Approach 1: Iterative Subtraction Approach

This approach is straightforward and simulates the process described in the problem. We repeatedly subtract the smaller number from the larger one until one of them becomes zero. This is similar to the Euclidean algorithm for computing the GCD, except that instead of computing a remainder, we're just performing subtraction until one number reaches zero.

Python

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

print(count_operations(10, 10))

Java

public class Solution {
    public int countOperations(int num1, int num2) {
        int count = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countOperations(10, 10));
    }
}

C++

#include <iostream>
using namespace std;

int countOperations(int num1, int num2) {
    int count = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
        count++;
    }
    return count;
}

int main() {
    int num1 = 10, num2 = 10;
    cout << countOperations(num1, num2);
    return 0;
}

JavaScript

function countOperations(num1, num2) {
    let count = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
        count++;
    }
    return count;
}

console.log(countOperations(10, 10));

#include <stdio.h>

int countOperations(int num1, int num2) {
    int count = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
        count++;
    }
    return count;
}

int main() {
    int num1 = 10, num2 = 10;
    printf("%d", countOperations(num1, num2));
    return 0;
}

using System;

public class Solution {
    public int CountOperations(int num1, int num2) {
        int count = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
            count++;
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountOperations(10, 10));
    }
}

The Python solution also uses a while loop. Depending on whether num1 is greater than or equal to num2, we subtract the smaller number from the larger. Each subtraction is a single operation tracked by count.

Complexity

Time Complexity: O(max(num1, num2)) because we are performing a subtraction operation in every loop iteration. Space Complexity: O(1) because we only require a constant amount of additional space.

Try this approach in the editor

Approach 2: Using Modulus Operation

An optimized solution is based on using modulus to perform the subtraction in a more efficient manner, similar to the Euclidean algorithm for GCD. Instead of subtracting consecutively, we use the modulus operation to reduce the larger number directly, which minimizes the number of operations.

Python

def count_operations(num1, num2):
    count = 0
    while num1 != 0 and num2 != 0:
        if num1 > num2:
            count += num1 // num2
            num1 %= num2
        else:
            count += num2 // num1
            num2 %= num1
    return count

print(count_operations(10, 10))

Java

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countOperations(10, 10));
    }
}

C++

#include <iostream>
using namespace std;

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

int main() {
    int num1 = 10, num2 = 10;
    cout << countOperations(num1, num2);
    return 0;
}

JavaScript

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

console.log(countOperations(10, 10));

#include <stdio.h>

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

int main() {
    int num1 = 10, num2 = 10;
    printf("%d", countOperations(num1, num2));
    return 0;
}

using System;

public class Solution {
    public int CountOperations(int num1, int num2) {
        int count = 0;
        while (num1 != 0 && num2 != 0) {
            if (num1 > num2) {
                count += num1 / num2;
                num1 %= num2;
            } else {
                count += num2 / num1;
                num2 %= num1;
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountOperations(10, 10));
    }
}

This Python code optimizes the operation count by applying integer division and modulus. We accumulate the quotient as the count of operations and use the modulus to get the new reduced number efficiently.

Complexity

Time Complexity: O(log(min(num1, num2))) reflecting the efficient reduction of number size. Space Complexity: O(1).

Try this approach in the editor

Approach 3: Simulation

We can directly simulate this process by repeatedly performing the following operations:

If num1 \ge num2, then num1 = num1 - num2;
Otherwise, num2 = num2 - num1.
Each time an operation is performed, increment the operation count by one.

When either num1 or num2 becomes 0, stop the loop and return the operation count.

The time complexity is O(m), where m is the maximum of num1 and num2. The space complexity is O(1).

TypeScript

function countOperations(num1: number, num2: number): number {
    let ans = 0;
    for (; num1 && num2; ++ans) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
    }
    return ans;
}

func countOperations(num1 int, num2 int) (ans int) {
	for ; num1 != 0 && num2 != 0; ans++ {
		if num1 >= num2 {
			num1 -= num2
		} else {
			num2 -= num1
		}
	}
	return
}

Rust

impl Solution {
    pub fn count_operations(mut num1: i32, mut num2: i32) -> i32 {
        let mut ans = 0;
        while num1 != 0 && num2 != 0 {
            ans += 1;
            if num1 >= num2 {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
        }
        ans
    }
}

Try this approach in the editor

Approach 4: Mathematics

Following the simulation process in Solution 1, we notice that if num1 is much larger than num2, each operation will only reduce the value of num1 slightly, leading to an excessive number of operations. We can optimize this process by directly adding the quotient of num1 divided by num2 to the answer in each operation, then taking the remainder of num1 divided by num2. This reduces the number of operations.

The time complexity is O(log m), where m is the maximum of num1 and num2. The space complexity is O(1).

TypeScript

function countOperations(num1: number, num2: number): number {
    let ans = 0;
    while (num1 && num2) {
        if (num1 >= num2) {
            ans += (num1 / num2) | 0;
            num1 %= num2;
        } else {
            ans += (num2 / num1) | 0;
            num2 %= num1;
        }
    }
    return ans;
}

func countOperations(num1 int, num2 int) (ans int) {
	for num1 != 0 && num2 != 0 {
		if num1 >= num2 {
			ans += num1 / num2
			num1 %= num2
		} else {
			ans += num2 / num1
			num2 %= num1
		}
	}
	return
}

Rust

impl Solution {
    pub fn count_operations(mut num1: i32, mut num2: i32) -> i32 {
        let mut ans = 0;
        while num1 != 0 && num2 != 0 {
            if num1 >= num2 {
                ans += num1 / num2;
                num1 %= num2;
            } else {
                ans += num2 / num1;
                num2 %= num1;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Subtraction Approach	Time Complexity: O(max(num1, num2)) because we are performing a subtraction operation in every loop iteration. Space Complexity: O(1) because we only require a constant amount of additional space.
Using Modulus Operation	Time Complexity: O(log(min(num1, num2))) reflecting the efficient reduction of number size. Space Complexity: O(1).
Simulation	–
Mathematics	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Subtraction (Simulation)	O(max(num1, num2))	O(1)	Best for understanding the problem mechanics or implementing a direct simulation
Modulus / Euclidean Optimization	O(log(min(num1, num2)))	O(1)	Preferred for large numbers and optimal interview solutions

Frequently asked questions

Is Count Operations to Obtain Zero easy or hard?

Count Operations to Obtain Zero is classified as an Easy problem. The basic simulation is straightforward to implement, while the optimized modulus approach introduces a useful insight related to the Euclidean algorithm for more efficient solutions.

Count Operations to Obtain Zero Python/Java solution

Both Python and Java implementations follow the same logic: repeatedly subtract the smaller value from the larger or apply the modulus optimization. The optimized version updates the count using division and replaces the larger number with the remainder until one value becomes zero.

How to solve Count Operations to Obtain Zero in O(log n)?

Use a modulus-based optimization similar to the Euclidean GCD algorithm. If num1 > num2, add num1 / num2 to the operation count and update num1 = num1 % num2. Otherwise perform the same step for num2. Each iteration significantly reduces the numbers, giving logarithmic time complexity.

What is the best approach for Count Operations to Obtain Zero?

The modulus-based approach derived from the Euclidean algorithm is the most efficient. Instead of subtracting the smaller number repeatedly, it counts how many subtractions happen using division and updates the value with the remainder. This reduces the time complexity to O(log(min(num1, num2))) while keeping O(1) space.

Is Count Operations to Obtain Zero asked at Google/Amazon/Meta?

Problems based on repeated subtraction and Euclidean-style optimizations appear frequently in coding interviews. Variants of this logic show up at companies like Amazon and Google when testing understanding of number operations, loops, and algorithmic optimization.

What data structure is used in Count Operations to Obtain Zero?

No specialized data structure is required. The problem relies on simple integer arithmetic and control flow. The optimized solution uses mathematical properties and modulus operations rather than arrays, stacks, or hash maps.

What is the time complexity of Count Operations to Obtain Zero?

The basic simulation solution runs in O(max(num1, num2)) time because it subtracts one step at a time. The optimized solution uses division and modulus to skip repeated subtractions, reducing the complexity to O(log(min(num1, num2))). Both approaches use constant O(1) extra space.

Count Operations to Obtain Zero solution and explanation

The problem

Approach overview

Approach 1: Iterative Subtraction Approach

Approach 2: Using Modulus Operation

Approach 3: Simulation

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Operations to Obtain Zero solution and explanation

The problem

Approach overview

Approach 1: Iterative Subtraction Approach

Approach 2: Using Modulus Operation

Approach 3: Simulation

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems