Java Solution Using Binary Search


  • 0
    A

    Worst case time complexity is O(nlgn) where n is the number of bits to represent dividend.

    public int divide(final int dividend, final int divisor) {
            long x = dividend, y = divisor;
    
            boolean isPositive = !((x >= 0) ^ (y >= 0));  // equivalent to (x >= 0 && y >= 0) || (x < 0 && y < 0)
    
            x = x < 0 ? -x : x;
            y = y < 0 ? -y : y;
    
            long result = 0;
    
            while (x >= y) {
                long power = findLargestPower(x, y);
                result += (1L << power);
                x -= (y << power);
            }
    
            result = isPositive ? result : -result;
    
            return result >= Integer.MAX_VALUE || result < Integer.MIN_VALUE ? Integer.MAX_VALUE : (int) result;
        }
    
        private long findLargestPower(final long x, final long y) {
            long left = 1, right = Integer.MAX_VALUE;
            while (left <= right) {
                long mid = left + (right - left)/2;
                if ((y << mid) >= (y << (mid-1)) && (y << mid) <= x) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
            return left-1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.