Divide Two Integers without using Multiplication, Division and Modulus Operator - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given two integers: dividend and divisor. Your task is to divide them without using the multiplication (*), division (/) or modulus (%) operators.

You should return the quotient after dividing dividend by divisor, discarding the fractional part.

Assume both numbers are positive and the division is always valid (i.e., divisor is never zero).

Examples❯

dividend divisor Output Description
10 3 3 10 divided by 3 is 3.33; discard fractional part, result is 3
15 5 3 15 divided by 5 is exactly 3
7 2 3 7 / 2 is 3.5, return only integer part 3
1 1 1 1 divided by 1 is 1
0 7 0 0 divided by any positive number is 0
100 10 10 Clean division: 100 / 10 = 10
1000 1 1000 Any number divided by 1 is itself
99 99 1 Equal numbers divide to give 1
5 10 0 Dividing a smaller number by a larger one gives 0
"" 3 0 Empty string for dividend is treated as 0
100 "" 0 Empty divisor should be invalid, but assumed 0 gives 0 in this mock setup

Solution❯

Understanding the Problem

We are given two positive integers: dividend and divisor. Our goal is to compute how many times the divisor fits into the dividend — that is, perform integer division — but without using multiplication (*), division (/), or modulus (%) operators.

For example, if dividend = 15 and divisor = 3, the answer should be 5 because 3 fits exactly 5 times into 15.

We are asked to discard the fractional part, which means this is integer division. For example, 10 / 3 should return 3 — not 3.33.

Step-by-Step Solution with Example

step 1: Initialize Result

We start by initializing a variable called result = 0. This will eventually hold our answer — the number of times the divisor fits into the dividend.

step 2: Loop While Dividend ≥ Divisor

As long as the dividend is greater than or equal to the divisor, we will try to subtract some multiple of the divisor from it.

step 3: Use Doubling to Speed Up

We use two variables: temp = divisor and multiple = 1. Now, we try to double temp (i.e., temp = temp << 1) and also double multiple as long as temp << 1 is still less than or equal to the dividend.

This doubling helps us speed up the subtraction by jumping bigger steps instead of subtracting the divisor one at a time.

step 4: Subtract and Add to Result

Once we can’t double further, we subtract temp from dividend, and we add multiple to result.

step 5: Repeat Until Done

We repeat steps 2–4 until the dividend becomes smaller than the divisor.

step 6: Return Result

After the loop, result will hold our answer — the integer quotient.

Example: Divide 15 by 3

  • Start with dividend = 15, divisor = 3
  • First round of doubling:
    • temp = 3 → 6 → 12 (next would be 24 which is > 15, so stop)
    • multiple = 1 → 2 → 4
  • Subtract 12 from 15 → new dividend = 3
  • Add 4 to result → result = 4
  • Next round: temp = 3, multiple = 1
  • 3 ≤ 3, subtract → dividend = 0, result = 5

Final Result: 5

Edge Cases

  • Dividend < Divisor: The result is 0 since the divisor doesn’t fit even once.
  • Dividend == Divisor: The result is 1 because it fits exactly once.
  • Large Inputs: Bit manipulation makes this method efficient even for large values of dividend.

Final Thoughts

This approach avoids the use of multiplication, division, and modulus by using subtraction and efficient bitwise operations like left shift. For beginners, understanding the intuition of "doubling the divisor" is key. It’s like subtracting in chunks — instead of one by one, we remove 2s, 4s, 8s, and so on to reach the target faster.

It's efficient and safe, and a powerful trick to add to your coding toolbox!

Algorithm Steps❯

  1. Initialize a variable result to 0. This will hold the final quotient.
  2. While dividend is greater than or equal to divisor:
    • Set temp = divisor and multiple = 1.
    • Keep doubling temp (left shift) and multiple as long as dividend >= (temp << 1).
    • Subtract temp from dividend and add multiple to result.
  3. Return result as the final quotient.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int divide(int dividend, int divisor) {
    int result = 0;
    while (dividend >= divisor) {
        int temp = divisor, multiple = 1;
        while (dividend >= (temp << 1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        dividend -= temp;
        result += multiple;
    }
    return result;
}

int main() {
    int dividend = 43;
    int divisor = 8;
    int quotient = divide(dividend, divisor);
    printf("Quotient of %d / %d = %d\n", dividend, divisor, quotient);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(log² N)In the best case, the dividend is just slightly larger than the divisor. The algorithm still performs a loop where the divisor is doubled each time (log N steps), and within each subtraction step, it performs another loop to find the largest double. Hence, the overall time is O(log² N).
Average CaseO(log² N)Each iteration of the outer loop subtracts the largest possible double of the divisor from the dividend. For each such subtraction, we double the divisor (which takes O(log N) time). This happens for O(log N) times, resulting in O(log² N) total time complexity.
Worst CaseO(log² N)Even in the worst case, the algorithm performs doubling operations and subtractions that take logarithmic time per step, and this process repeats log N times. So the worst-case time complexity remains O(log² N).

Space Complexity❯

O(1)

Explanation: Only a constant number of variables are used for computation (e.g., result, temp, multiple), and no additional space scales with the size of input. Hence, the space complexity is constant.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...