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!
Comments
Loading comments...