Divide two integers without using multiplication, division and mod operator

The problem, simply

You get two whole numbers, dividend and divisor. Give back dividend / divisor, rounded toward zero, so 3.7 becomes 3 and -3.5 becomes -3.

You may not use *, / or %. You may add, subtract and shift bits. If the true answer is too big for an int, give back Integer.MAX_VALUE.

A story to remember it

Picture it

Examples

Way 1: the simple way

Division is taking away the same amount again and again.

1. Handle the overflow case first.
2. Remember whether the answer is negative: it is when exactly one of the two numbers is negative.
3. Make both numbers positive, inside a long so -2147483648 fits.
4. Subtract the divisor until what is left is smaller than it, counting each time.

class Solution {
    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean negative = (dividend < 0) ^ (divisor < 0);
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        long packs = 0;
        while (a >= b) {
            a -= b;            // fill one pack
            packs++;
        }
        return (int) (negative ? -packs : packs);
    }
}

How long it takes: one round per pack, O(dividend / divisor). Dividing 2 billion by 1 takes 2 billion rounds. Extra room: O(1).

Way 2: the clever way

b << i is b doubled i times, a box of 2^i packs. Try the boxes from the biggest down. Each box is used at most once, because if two boxes of size 2^i fit, one box of size 2^(i+1) would have fit first.

1. Handle overflow, the sign, and make both numbers positive longs.
2. For i from 31 down to 0: if b << i fits in what is left, take it away and switch on bit i of the answer.
3. Put the sign back.

class Solution {
    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean negative = (dividend < 0) ^ (divisor < 0);
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        long packs = 0;
        for (int i = 31; i >= 0; i--) {
            if ((b << i) <= a) {      // a box of 2^i packs fits
                a -= b << i;          // take it away
                packs += 1L << i;     // switch on bit i of the answer
            }
        }
        return (int) (negative ? -packs : packs);
    }
}

How long it takes: exactly 32 tries, one per bit of the answer, O(log n). Extra room: O(1).

Watch out for

• Rounding the wrong way. Java's / rounds toward zero, and so does dividing the positive values and putting the sign back. Do not round down for negatives.
• Shifting in int. 7 << 30 overflows an int. Do the shifts in long, where even 2^31 << 31 fits.
• Dividing by zero. The problem usually promises the divisor is not 0. If not, throw an ArithmeticException.

What interviewers ask next

• Another fast way? Double the divisor until it is too big, take away the biggest double that fits, and repeat. That is O(log^2 n), since each round rebuilds the doubles.
• What if you may only use 32 bit ints, no long? Turn both numbers negative instead, since an int holds one more negative value than positive ones, and flip every comparison.
• How would you get the remainder too? It is whatever is left in a at the end, with the sign of the dividend.
• Multiply without *? The mirror trick: add a << i for every bit i that is on in b.

Remember this

Grown-up words: the boxes of packs are shifted divisors, filling the biggest box first is binary long division, the leftover is the remainder, and the special case is integer overflow.