2169. Count Operations to Obtain Zero

[mah-shamim]

Topics: Math, Simulation, Weekly Contest 280

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⁵

Hint:

1. Try simulating the process until either of the two integers is zero.
2. Count the number of operations done.

[mah-shamim]

We need to determine the number of operations required to reduce either of two given non-negative integers to zero by repeatedly subtracting the smaller number from the larger one. The operations continue until one of the numbers becomes zero.

Approach

1. Simulation with Optimization: Instead of simulating each subtraction step one by one (which could be inefficient for large numbers), we use integer division to calculate how many operations can be performed in one go.
2. Efficient Subtraction: For each step, if num1 is greater than or equal to num2, we calculate how many times num2 can be subtracted from num1 using integer division. This count is added to the total operations, and num1 is updated to the remainder of num1 divided by num2. Similarly, if num2 is larger, we do the same for num2 using num1.
3. Termination Check: The loop continues until either num1 or num2 becomes zero. The total count of operations performed is then returned.

Let's implement this solution in PHP: 2169. Count Operations to Obtain Zero

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function countOperations($num1, $num2) {
    $count = 0;
    while ($num1 > 0 && $num2 > 0) {
        if ($num1 >= $num2) {
            $count += intdiv($num1, $num2);
            $num1 %= $num2;
        } else {
            $count += intdiv($num2, $num1);
            $num2 %= $num1;
        }
    }
    return $count;
}

// Test cases
echo countOperations(2, 3) . PHP_EOL;   // Output: 3
echo countOperations(10, 10) . PHP_EOL; // Output: 1
?>

Explanation:

1. Initialization: We start with a count of zero operations.
2. Loop Execution: The loop runs as long as both numbers are non-zero. In each iteration:
   • If num1 is greater than or equal to num2, we compute how many times num2 can be subtracted from num1 using integer division. This quotient is added to the count, and num1 is updated to the remainder of num1 divided by num2.
   • If num2 is greater than num1, we compute how many times num1 can be subtracted from num2 similarly, update the count, and set num2 to the remainder.
3. Termination: Once either num1 or num2 becomes zero, the loop exits, and the total count of operations is returned.

[basharul-siddike]

Thanks for solving the problem of "Count Operations to Obtain Zero"

[mah-shamim]

Thanks