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 thenumber of operations required to make either num1 = 0 or num2 = 0.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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^5

Solution

Method 1 – Simulation with Greedy Subtraction

Intuition

At each step, subtract the smaller number from the larger one. This is equivalent to repeatedly applying the Euclidean algorithm, counting the number of subtractions needed to make either number zero.

Approach

  1. Initialize a counter for the number of operations.
  2. While both numbers are nonzero:
    • If num1 >= num2, subtract num2 from num1 and increment the counter.
    • Else, subtract num1 from num2 and increment the counter.
  3. Return the counter when either number becomes zero.

Code

 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
13

func CountOperations(num1, num2 int) int {
    ans := 0
    for 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

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

class Solution {
    fun countOperations(num1: Int, num2: Int): Int {
        var a = num1; var b = num2; var ans = 0
        while (a > 0 && b > 0) {
            if (a >= b) {
                ans += a / b
                a %= b
            } else {
                ans += b / a
                b %= a
            }
        }
        return ans
    }
}
 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

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

class Solution {
    countOperations(num1: number, num2: number): number {
        let ans = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) {
                ans += Math.floor(num1 / num2);
                num1 %= num2;
            } else {
                ans += Math.floor(num2 / num1);
                num2 %= num1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log(max(num1, num2))), since each step reduces one of the numbers, similar to the Euclidean algorithm.
  • 🧺 Space complexity: O(1), since only a constant amount of space is used.