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.
Input: dividend = 10, divisor = 3
This challenge need to handle corner overflow cases carefully.
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].
Another corner case is when
divisor is different signed, we need to convert them to
According to Note #1, we can not use
abs function directly, since
abs(MIN_INT) will introduce overflow. So we convert
long long data type, which will be safe for reversing the negative value into positive value.
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
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:
A more understandable logic is, because an integer could be represented in 32 bits.
Preparing for an interview? Check out this!