Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Divide Two Integers

Divide Two Integers

Master this topic with zero to advance depth.

Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Hard

Examples

Input: dividend = 10, divisor = 3
Output: 3

10/3 = 3.33333... which is truncated to 3.

Input: dividend = 7, divisor = -3
Output: -2

7/-3 = -2.33333... which is truncated to -2.

Approach 1

Level I: Brute Force (Linear Subtraction)

Intuition

Keep subtracting the divisor from the dividend until the dividend becomes smaller than the divisor. The number of times we subtract is the quotient.

Thought Process

  1. Handle edge cases (overflow for INT_MIN).
  2. Determine sign of result.
  3. Take absolute values of dividend and divisor.
  4. Loop while dividend >= divisor:
    • dividend -= divisor.
    • count++.
  5. Apply sign and return.

Pattern: Simulation

⏱ O(N) - Where $N$ is the quotient. Extremely slow for large dividends.💾 O(1) - Constant space.
java
public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);
        int res = 0;
        while (dvd >= dvs) {
            dvd -= dvs;
            res++;
        }
        return (dividend > 0) == (divisor > 0) ? res : -res;
    }
}
Approach 2

Level II: Recursive Long Division

Intuition

The exponential subtraction can be performed recursively. In each call, we find the largest multiple of the divisor that can be subtracted and then recurse on the remainder.

⏱ $O(\log^2 N)$💾 $O(\log N)$ (Recursion stack)
java
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long dvd = Math.abs((long)dividend), dvs = Math.abs((long)divisor);
        long res = ldivide(dvd, dvs);
        return (dividend > 0) == (divisor > 0) ? (int)res : (int)-res;
    }
    private long ldivide(long dvd, long dvs) {
        if (dvd < dvs) return 0;
        long sum = dvs, multiple = 1;
        while ((sum << 1) <= dvd) {
            sum <<= 1;
            multiple <<= 1;
        }
        return multiple + ldivide(dvd - sum, dvs);
    }
}
Approach 3

Level III: Optimal (Exponential Subtraction / Shifts)

Intuition

Instead of subtracting exactly one divisor at a time, we subtract the largest possible multiple of the divisor using bit shifts (divisor << k). This is equivalent to long division in binary.

Thought Process

  1. While dividend >= divisor:
    • Find the largest kk such that divisor << k <= dividend.
    • dividend -= (divisor << k).
    • quotient += (1 << k).
  2. This uses the property that B⋅2kB \cdot 2^k is a fast way to find large chunks to subtract.

Pattern: Exponential Backoff / Long Division

⏱ O(log^2 N) - Outer loop reduces dividend, inner loop finds shift.💾 O(1) - Constant space.

Detailed Dry Run

15 / 3

  • Largest shift: 3 << 2 = 12. 15 - 12 = 3. Quotient = 4 (2^2).
  • Largest shift: 3 << 0 = 3. 3 - 3 = 0. Quotient = 4 + 1 = 5. Result: 5
java
public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long a = Math.abs((long)dividend), b = Math.abs((long)divisor), res = 0;
        while (a >= b) {
            long temp = b, multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            res += multiple;
        }
        return (dividend > 0) == (divisor > 0) ? (int)res : (int)-res;
    }
}
← Previous QuestionMaximum XOR of Two Numbers in an Array
Next Question →Total Hamming Distance