2169. Count Operations to Obtain Zero

Approach

Simulate subtraction (equivalent to Euclidean GCD steps); count operations.

Key Techniques

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Simulation

Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.

2169.cs

// Approach: Simulate subtraction (equivalent to Euclidean GCD steps); count operations.
// Time: O(log(min)) Space: O(1)

public class Solution
{
    public int CountOperations(int num1, int num2)
    {
        // Initialize operation counter
        int operationCount = 0;

        // Continue operations while both numbers are non-zero
        while (num1 != 0 && num2 != 0)
        {
            // Subtract the smaller number from the larger number
            if (num1 >= num2)
                num1 -= num2;
            else
                num2 -= num1;

            // Increment the operation counter after each subtraction
            operationCount++;
        }

        // Return the total number of operations performed
        return operationCount;
    }
}

Was this solution helpful?