Skip to content

2169. Count Operations to Obtain Zero

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.

  • 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 <= 105

Solutions

Solution 1: Simulation

Thinking

Each step subtracts the smaller number from the larger until one is zero — Euclidean subtraction. Values are at most \(10^4\), so simulating every subtraction is fine.

Compare \(\textit{num1}\) and \(\textit{num2}\), subtract, and count.

Stop when either side is \(0\).

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

  • If \(\textit{num1} \ge \textit{num2}\), then \(\textit{num1} = \textit{num1} - \textit{num2}\);
  • Otherwise, \(\textit{num2} = \textit{num2} - \textit{num1}\).
  • Each time an operation is performed, increment the operation count by one.

When either \(\textit{num1}\) or \(\textit{num2}\) becomes \(0\), stop the loop and return the operation count.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                num1 -= num2
            else:
                num2 -= num1
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int countOperations(int num1, int num2) {
        int ans = 0;
        for (; num1 != 0 && num2 != 0; ++ans) {
            if (num1 >= num2) {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int countOperations(int num1, int num2) {
        int ans = 0;
        for (; num1 && num2; ++ans) {
            if (num1 >= num2) {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func countOperations(num1 int, num2 int) (ans int) {
    for ; num1 != 0 && num2 != 0; ans++ {
        if num1 >= num2 {
            num1 -= num2
        } else {
            num2 -= num1
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function countOperations(num1: number, num2: number): number {
    let ans = 0;
    for (; num1 && num2; ++ans) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var countOperations = function (num1, num2) {
    let ans = 0;
    for (; num1 && num2; ++ans) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
    }
    return ans;
};

Solution 2

Thinking

Solution 1 subtracts many times when one number dwarfs the other. Replacing repeated subtraction by division adds the quotient at once and continues with the remainder.

The number of iterations becomes \(O(\log m)\), as in the Euclidean algorithm.

The English write-up repeats this formulation under two headings; both match the modulo implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                ans += num1 // num2
                num1 %= num2
            else:
                ans += num2 // num1
                num2 %= num1
        return ans

Solution 2: Mathematics

Thinking

Solution 1 subtracts many times when one number dwarfs the other. Replacing repeated subtraction by division adds the quotient at once and continues with the remainder.

The number of iterations becomes \(O(\log m)\), as in the Euclidean algorithm.

This heading is the named write-up of the same modulo loop.

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        ans = 0
        while num1 and num2:
            if num1 >= num2:
                ans += num1 // num2
                num1 %= num2
            else:
                ans += num2 // num1
                num2 %= num1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int countOperations(int num1, int num2) {
        int ans = 0;
        while (num1 != 0 && num2 != 0) {
            if (num1 >= num2) {
                ans += num1 / num2;
                num1 %= num2;
            } else {
                ans += num2 / num1;
                num2 %= num1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int countOperations(int num1, int num2) {
        int ans = 0;
        while (num1 && num2) {
            if (num1 >= num2) {
                ans += num1 / num2;
                num1 %= num2;
            } else {
                ans += num2 / num1;
                num2 %= num1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var countOperations = function (num1, num2) {
    let ans = 0;
    while (num1 && num2) {
        if (num1 >= num2) {
            ans += (num1 / num2) | 0;
            num1 %= num2;
        } else {
            ans += (num2 / num1) | 0;
            num2 %= num1;
        }
    }
    return ans;
};

Comments