[Leetcode] Divide Integers

Problem 

Divide two integers without using multiplication, division and mod operator.

Algorithm

Exponential Solution

No multiplication, division and mode operator, we can only use addition and subtraction. 

The division a/b =x, is equivalent to a = b*x + r, where r < b is the remainder. Note 

                                                             b*x <= a < b*(x+1).

Therefore, we can use addition to calculate b*(x+1) until the first time it exceeds a. The worst case running time is O(a/b). When b is small, it is exponential to the number of digits of both a and b.  

Linear Solution 
Assume a*b >0.  Let x = 2^0 * x0 + 2^1 * x1 + ... 2^d * xd, then

                                     a = x0 * 2^0 * b +  x1 * 2^1 * b + ... +  xd * 2^d * b  + r.  (1)

If we can compute (x0, x1, ... xd), we can construct x. Divide 2^d * b on both side of equation (1), we have 

                                   xd = a / (b*2^d).                                                                    (2)

Then, we can recursively solve (a - xd * 2^d *b) / b. 

Integer Overflow

Since the Integer has range [-2^31, 2^31-1], the abs(Integer.max) = Integer.min. It is better to change a and b to negative integers first, then assign the correct sign to x. 

Bit 

Should Implement Bit Manipulation Approach. 

See Here 

Code