29. Divide Two Integers (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.

29. Divide Two Integers (#1 Binary search + recursion).java

// Binary search solution
// Time: O(logn) where n is the quotient, 1ms
// Space: O(1), 33,7mb
class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
            sign = -1;
        }
        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);
        
        long lans = ldivide(ldividend, ldivisor, sign);
        
        if(lans > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if(lans < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        } else {
            return (int)lans;
        }
    }
    
    // Recursion function
    private long ldivide(long ldividend, long ldivisor, int sign) {
        // Base case
        if(ldividend < ldivisor) {
            return 0;
        }
        
        long multiple = 1;
        long sum = ldivisor;
        while((sum + sum) < ldividend) {
            // Keep adding itself: d, d * 2, d * 4 ... until find the largest sum smaller than target
            multiple += multiple;
            sum += sum;
        }
        
        // Recursion calls
        if(sign == 1) {
            return multiple + ldivide(ldividend - sum, ldivisor, sign); 
        } else {
            return 0 - multiple + ldivide(ldividend - sum, ldivisor, sign);
        }
        
    }
}

29. Divide Two Integers (#2 Binary search + Bit manipulation).java

// Essentially the same as #1 but use bit manipulation to multiply sum by 2
// Time: O(logn)
// Space: O(1)
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean sign = (dividend > 0) ^ (divisor > 0);
        long dvd = Math.abs((long) dividend);
        long dvs = Math.abs((long) divisor);
        int res = 0;
        while (dvd >= dvs) {
            long temp = dvs;
            int multiple = 1;
            while (dvd >= (temp << 1)) {
                multiple <<= 1;
                temp <<= 1;
            }
            dvd -= temp;
            res += multiple;
        }
        return sign ? -res : res;
    }
}