Count Operations to Obtain Zero - Practice Coding Problems

Count Operations to Obtain Zero - Problem

Math Simulation Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: num1 = 2, num2 = 3

› Output: 3

💡 Note: Operation 1: 3 ≥ 2, so num2 = 3 - 2 = 1, now num1 = 2, num2 = 1. Operation 2: 2 ≥ 1, so num1 = 2 - 1 = 1, now num1 = 1, num2 = 1. Operation 3: 1 = 1, so num1 = 1 - 1 = 0. Total: 3 operations.

Example 2 — One Operation

$ Input: num1 = 10, num2 = 10

› Output: 1

💡 Note: Since both numbers are equal, one operation makes one of them zero: 10 - 10 = 0. Total: 1 operation.

Example 3 — Multiple Operations

$ Input: num1 = 1, num2 = 5

› Output: 5

💡 Note: 5-1=4, 4-1=3, 3-1=2, 2-1=1, 1-1=0. Total: 5 operations to make num1 zero.

Constraints

0 ≤ num1, num2 ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Two non-negative integers num1 and num2

Process

Keep subtracting smaller from larger until one becomes zero

Output

Total number of operations performed

Key Takeaway

🎯 Key Insight: This is the Euclidean algorithm in disguise - use division to optimize!

Asked in

A Amazon 15 G Google 12

The key insight is that this problem is essentially the Euclidean algorithm for finding GCD, but instead of finding the GCD, we count the total number of operations. The optimal approach uses division to calculate multiple subtractions at once rather than simulating each step. Time: O(log min(num1, num2)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Division Approach	O(log(min(num1, num2)))	O(1)	Use division to calculate multiple subtractions at once, similar to Euclidean algorithm
Simulation Approach	O(max(num1, num2))	O(1)	Simulate each subtraction operation until one number becomes zero

Optimized Division Approach — Algorithm Steps

Step 1: While both numbers are positive
Step 2: Add quotient (larger/smaller) to operations
Step 3: Replace larger with remainder (larger % smaller)
Step 4: Continue until one becomes zero

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with num1=10, num2=4

Division Step

10÷4=2 operations, remainder=2

Continue

4÷2=2 operations, remainder=0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int main() {
    int num1, num2;
    scanf("%d", &num1);
    scanf("%d", &num2);
    int result = solution(num1, num2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log(min(num1, num2)))

Similar to Euclidean algorithm, reduces numbers logarithmically

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables to track operations

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Division Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler