Division without using *, / or % (Divide Two Integers)

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

Thoughts:
The common way to do this is to count how many times that divisor adding up to dividend. Of course, we should take care of signs. That’s not hard though. However, LeetCode won’t let you pass for the reason of time exceed exception. I have to use nother trick: since \log(\frac{a}{b}) = \log{a} - \log{b}, we have \frac{a}{b} = \exp (\log{a} - \log{b}). The tricky part of this question does not lie on the algorithm though. It has something to do with overflows. For particular, if we use Math.abs to compute the absolute value of Integer.MIN(-2147483648), we get -2147483648 again. So we should manually make it equal to Integer.MAX(2147483647). Most of the cases this is fine, except for one case where you try to divide Integer.MIN by 2, i.e., -2147483648 / 2 = -1073741824. However, 2147483647 / 2 = 1073741823. I have to add one more edge condition that if the divisor is 2, we just do the bitwise operation: right shift. Another node is Integer.MAX / Integer.MIN = 0 (not -1).

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0)
            return 0;
        if(divisor == 1)
            return dividend;
        if(dividend == divisor)
            return 1;
        if(divisor == 2)
            return dividend >> 1;
            
        boolean sign = false;
        if( (dividend > 0 && divisor < 0) ||
            (dividend < 0 && divisor > 0) )
            sign = true;
            
        if(dividend == Integer.MAX_VALUE && divisor == Integer.MIN_VALUE)
            return 0;
        
        dividend = dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(dividend);
        divisor = divisor == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(divisor);
        int result = (int) Math.floor(Math.pow(Math.E, Math.log(dividend) - Math.log(divisor)));
        return sign ? -result : result;
    }
}

Code (C++):

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor == 0)
            return 0;
        if(divisor == 1)
            return dividend;
        if(dividend == divisor)
            return 1;
        if(divisor == 2)
            return dividend >> 1;
        
        bool sign = false;
        if( (dividend > 0 && divisor < 0) ||
            (dividend < 0 && divisor > 0))
            sign = true;
            
        if(dividend == numeric_limits<int>::max() 
            && divisor == numeric_limits<int>::min())
            return 0;
        
        dividend = dividend == numeric_limits<int>::min() ? 
                numeric_limits<int>::max() : abs(dividend);
        divisor = divisor == numeric_limits<int>::min() ? 
                numeric_limits<int>::max() : abs(divisor);
        
        int result = (int) floor(exp(log(dividend) - log(divisor)));
        return sign ? -result : result;
    }
};
About these ads

One Comment (+add yours?)

  1. Z
    Jul 09, 2013 @ 09:08:37

    No way the interviewer will like this solution.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 59 other followers

%d bloggers like this: