15 line easy understand solution. 129ms


  • 35
    L

    for example, if we want to calc (17/2)

    ret = 0;

    17-2 ,ret+=1; left=15

    15-4 ,ret+=2; left=11

    11-8 ,ret+=4; left=3

    3-2 ,ret+=1; left=1

    ret=8;

    class Solution:
    # @return an integer
    def divide(self, dividend, divisor):
        isMinus= ((dividend<0 and divisor >0) or (dividend>0 and divisor <0));
        ret=0;        
        dividend,divisor=abs(dividend),abs(divisor);
        c,sub=1,divisor;
    
        while(dividend >= divisor):
            if(dividend>=sub):
                dividend-=sub;
                ret+=c;
                sub=(sub<<1);
                c=(c<<1);
            else:
                sub=(sub>>1);
                c=(c>>1);
        
        if(isMinus):
            ret=-ret;
        return min(max(-2147483648,ret),2147483647);

  • 2
    R

    Why are there down votes for this answer? It works. It helps me. I will upvote it once to counteract the downvotes.


  • 1
    L

    Thanks, I also don't know why , :).


  • 14
    R

    I did not vote on this solution, the reason of down vote is probably because that

    1. you used multiplication and division and
    2. you did not deal with overflow.

    For example

    abs(dividend) 
    

    and

    ret=-ret
    

    are problematic for C/C++ and less problematic for Python. Even though your code is accepted, it is not what the interviewer want to see. Here is why

    The range of integer is normally between -2^(n-1) to 2^(n-1) - 1, for c/c++/python n is 32 by default.
    Therefore

    abs(-2^(n-1))
    

    will still give you -2^(n-1) in C/C++

    The reason you can get AC for this problem is that python can do some automatic conversions from 32bit int to 64bit long.


  • 1
    L

    I update the code to not directly use *2 , /2


  • 0
    L

    I voted it because the idea was simple and easy to understand.
    I was not sure with the time complexity, looked like O(lg(n)), it would be better if you could give further analysis.


  • 0
    S

    It doesn't work when divisor = 0.


  • 0
    O

    Thanks for explaining! I always got frustrated on this kind of solution because Python has different handling than C and I'm not sure about how to answer the question using Python!


  • 0

    Can someone explain why we need to do bit shifting?


  • 0
    S

    It just a divide by two or multiply by two.


  • 0
    M

    I'd add a divide-by-zero handler, e.g.:

            if divisor == 0:
                raise ZeroDivisionError('division by zero')
    

    Other than that and some formatting quibbles that don't affect operation (sub<<=1 works just as well as sub=(sub<<1), etc., and PEP8 things), this code does the job well.

    (I liked the the isMinus and return value calculations - compact but readable.)


  • 0

    Rewrite into a JAVA solution for reference. I am not using Long type so I add several cases to do with the overflow...

    public class Solution {
        public int divide(int dividend, int divisor) {
            if (dividend == divisor) return 1;
            if (dividend == 0 || divisor == Integer.MIN_VALUE) return 0;
            if (dividend > 0 && divisor > 0 && dividend < divisor) return 0;
            if (dividend < 0 && divisor < 0 && dividend > divisor) return 0;
            if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
            if (dividend == Integer.MIN_VALUE && divisor == 1) return Integer.MIN_VALUE;
            int sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) ? -1 : 1;
            int power = 1;
            int out = 0;
            divisor = Math.abs(divisor);
            int subtractor = divisor;
            if (dividend == Integer.MIN_VALUE) {
                dividend = Integer.MAX_VALUE - subtractor + 1;
                out += power;
            }
            dividend = Math.abs(dividend);
            while (dividend >= divisor) {
                if (dividend >= subtractor) {
                    dividend -= subtractor;
                    out += power;
                    subtractor = subtractor << 1;
                    power = power << 1;
                }
                else {
                    subtractor = subtractor >> 1;
                    power = power >> 1;
                }
            }
            return sign == 1 ? out : -out;
        }
    }
    

  • 0
    S

    Genius code and solution! Really impressive!


  • 0
    R

    abs(dividend): what if dividend is INT_MIN? Can you take absolute value like that?


Log in to reply
 

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