Relatively Straightforward Java Solution that beats 78%


  • 1
    A

    So basically what this does is shifts the divisor by a large initial amount. I used 31 since we are dealing with integers, which are 32 bits. Then, if the shifted divisor <= dividend, we move stop and subtract the dividend by the shifted divisor. The shifted divisor will be of the form divisor * 2^k. We keep track of k, and keep adding our result by (1L << k). We don't need to check larger k's once we decrement it to a certain point, because the dividend keeps getting smaller. We also get rid of overflow errors by using longs. This is essentially the method found in Elements of Programming Interviews.

    public class Solution {
        public int divide(int dividend, int divisor) {
            long x = dividend;
            long y = divisor;
    
            // Take the absolute values and deal with the sign later.
            // This is a potential overflow point, so we need to use longs. 
            // For example, if we have Integer.MIN_VALUE, taking the 
            // absolute value of that will overflow.
            x = Math.abs(x);
            y = Math.abs(y);
            int power = 31;
    
            // will likely overflow since we're shifting left by 31. 
            long yPower = y << power;
            long result = 0;
    
            // Stop once the dividend is less than the divisor. 
            // We clearly cannot fit anymore integer multiples of 
            // the divisor into the dividend.
            while(x >= y) {
    
                // We still haven't found a candidate <= dividend.
                while(yPower > x) {
                    yPower >>= 1;
                    power--;
                }
    
                x -= yPower;
    
                // we multiplied the divisor by 2^power, so this is how
                // much we can increment result. 
                result += (1L << power);
            }
    
            // check if they have the same sign.
            result = (dividend > 0) ^ (divisor > 0) ? 0 - result : result;
    
            // overflow checks. If overflowed, then return max value. 
            return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE ? Integer.MAX_VALUE : (int) result;
        }
    

Log in to reply
 

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