Bit ManipulationProblem 8 of 10

Divide two integers without using multiplication, division and mod operator

Brute Force
Time: O(dividend)
Space: O(1)
Optimal
Time: O(log^2 N)
Space: O(1)

Problem Statement

Divide two integers without using multiplication (*), division (/), or mod (%) operators. Return the quotient after dividing dividend by divisor. The result should truncate toward zero.

Example:

Input: dividend = 43, divisor = 8 Output: 5 Explanation: 43 / 8 = 5.375, truncated to 5 Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10 / 3 = 3.333, truncated to 3 Input: dividend = -7, divisor = 2 Output: -3 Explanation: -7 / 2 = -3.5, truncated to -3

Noob-Friendly Explanation

Imagine you have 43 candies and you want to distribute them equally into bags of 8. You keep putting 8 candies into a bag until you don't have enough for another full bag. You made 5 bags, with 3 left over. So 43 ÷ 8 = 5.

But we can't use division! So the brute force way is to keep subtracting 8 from 43 over and over: 43→35→27→19→11→3. That's 5 subtractions, so the answer is 5.

The optimal trick: instead of subtracting 8 one at a time, subtract in bigger chunks using bit shifting. 8, 16, 32... (doubling the divisor) to speed things up dramatically.

Approach 1: Brute Force (Repeated Subtraction)

Intuition

Division is just repeated subtraction. Keep subtracting the divisor from the dividend and count how many times.

Algorithm

  1. Handle signs separately — work with absolute values
  2. Keep subtracting divisor from dividend
  3. Count the number of subtractions
  4. Apply the correct sign to the result
java
class Solution {
    public static int divide(int dividend, int divisor) {
        if (divisor == 0) throw new ArithmeticException("Division by zero");

        // Handle overflow case
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // Determine sign of result
        boolean negative = (dividend < 0) ^ (divisor < 0);

        // Work with positive values using long to avoid overflow
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        int quotient = 0;
        while (absDividend >= absDivisor) {
            absDividend -= absDivisor;
            quotient++;
        }

        return negative ? -quotient : quotient;
    }

    public static void main(String[] args) {
        System.out.println(divide(43, 8));   // 5
        System.out.println(divide(10, 3));   // 3
        System.out.println(divide(-7, 2));   // -3
        System.out.println(divide(1, 1));    // 1
    }
}

Complexity Analysis

  • Time Complexity: O(dividend) — In the worst case, we subtract 1 each time (dividend / 1)
  • Space Complexity: O(1) — Only using a few variables

Approach 2: Optimal (Bit Shifting / Exponential Subtraction)

Intuition

Instead of subtracting the divisor one at a time, we double it using bit shifts to subtract in larger chunks. For each step, find the largest multiple of divisor (that is a power of 2 × divisor) that fits into the remaining dividend.

Example: 43 ÷ 8

  • 8 << 2 = 32 <= 43, so subtract 32 and add 4 to quotient. Remaining: 11
  • 8 << 0 = 8 <= 11, so subtract 8 and add 1 to quotient. Remaining: 3
  • 3 < 8, stop. Quotient = 4 + 1 = 5

Algorithm

  1. Handle edge cases (divisor = 0, overflow)
  2. Determine the sign
  3. While dividend ≥ divisor:
    • Find the largest shift s where divisor << s ≤ dividend
    • Subtract divisor << s from dividend
    • Add 1 << s to quotient
  4. Apply sign and return
java
class Solution {
    public static int divide(int dividend, int divisor) {
        if (divisor == 0) throw new ArithmeticException("Division by zero");

        // Handle overflow: Integer.MIN_VALUE / -1 would overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // Determine sign
        boolean negative = (dividend < 0) ^ (divisor < 0);

        // Use long to handle absolute value of Integer.MIN_VALUE
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        int quotient = 0;

        while (absDividend >= absDivisor) {
            // Find the largest shift where divisor << shift <= dividend
            long tempDivisor = absDivisor;
            int shift = 0;

            while (tempDivisor <= absDividend) {
                tempDivisor <<= 1;
                shift++;
            }
            // tempDivisor overshot, so use shift-1
            shift--;

            // Subtract and add to quotient
            absDividend -= (absDivisor << shift);
            quotient += (1 << shift);
        }

        return negative ? -quotient : quotient;
    }

    public static void main(String[] args) {
        System.out.println(divide(43, 8));    // 5
        System.out.println(divide(10, 3));    // 3
        System.out.println(divide(-7, 2));    // -3
        System.out.println(divide(100, 5));   // 20
        System.out.println(divide(0, 5));     // 0
    }
}

Complexity Analysis

  • Time Complexity: O(log² N) — Outer loop runs O(log N) times, inner loop also O(log N)
  • Space Complexity: O(1) — Only using a few variables

Key Takeaways

  1. Left Shift = Multiply by 2: divisor << k is the same as divisor * 2^k
  2. Greedy Approach: Always subtract the largest possible chunk first
  3. Overflow Edge Case: Integer.MIN_VALUE / -1 overflows in 32-bit — must handle explicitly
  4. Sign Handling: XOR of signs tells us if result is negative: (a < 0) ^ (b < 0)
Previous
Copy set bits in a range
Next
Calculate square of a number without using multiplication, division and pow()