Description

https://leetcode.com/problems/divide-two-integers/

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

Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.

Example 1:

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

Example 2:

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

Solution

This challenge need to handle corner overflow cases carefully.

Note #1

We first notice that when dividend eq MIN_INT and divisor eq -1, the result will overflow since the integer range is [-(2^31), 2^31-1].

Note #2

Another corner case is when dividend and divisor is different signed, we need to convert them to abs values.

According to Note #1, we can not use abs function directly, since abs(MIN_INT) will introduce overflow. So we convert int into long long data type, which will be safe for reversing the negative value into positive value.

long long a = abs((long long)dividend);
long long b = abs((long long)divisor);

The naive algorithm

Without multiplication, division, and mod operator, we could come out with a naive solution, we use add operator to test how many times divisor added into a sum, which less or equal to dividend.

long long cur = 0;
int result = 0;
while(cur + divisor <= dividend) {
  cur += divisor;
  result++;
}

But this will be very slow, especially when dividend is very large value and divisor is small.

The algorithm with bits operation

Bits operation could be used to time performance.

We observe that: when (value>>i) / divisor = cnt, we could get (value/divisor) = (cnt<<i).

So we iterate each bits and accumulate to the final result:

#define MAX 2147483647
#define MIN (-2147483648)
class Solution {
public:
    int divide(int dividend, int divisor) {
        assert(divisor != 0);
        if(dividend == MIN && divisor == -1) return MAX;
        bool rev = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long long a = abs((long long)dividend);
        long long b = abs((long long)divisor);
        long long result = 0;

        while(a >= b) {
            long long c = b;
            for(int i=0; a >= c; ++i, c <<= 1) {
                a -= c;
                result += (1 << i);
            }
        }


        return rev ? (-result) : (result);
    }
};

A more understandable logic is, because an integer could be represented in 32 bits.

for (int i = 31; i >= 0; i--) {
  if ((a >> i) >= b) {
    a -= (b << i);
    result += (1 << i);
  }
}

Preparing for an interview? Check out this!