Leetcode 29: Divide Two Integers

 

Code (Naive)

import sys


class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if not divisor: return sys.maxint
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        dividend, divisor = abs(dividend), abs(divisor)

        res = 0
        while dividend - divisor >= 0:
            dividend -= divisor
            res += 1

        return res * sign

This is  a naive solution, where you count how many times dividend is to divisor by subtracting divisor from dividend until dividend < divisor. This solution causes Time Limit Error when dividend is large and divisor is small.

 

Code

import sys

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if not divisor: 
            return sys.maxint
        
        # In python there is no overflow issue.
        # This condition is here for a specific test case.
        if (dividend == -2**31 and divisor == -1):
            return 2**31-1
        
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        dividend, divisor = abs(dividend), abs(divisor)
    
        res = 0
        while dividend >= divisor:
            tmp_divisor = divisor
            tmp_multiple = 1
            while dividend >= (tmp_divisor << 1):
                tmp_divisor <<= 1
                tmp_multiple <<= 1
                
            dividend -= tmp_divisor
            res += tmp_multiple
        
        return res * sign

 

Idea

This is a quicker way to do the division. You approach to the quotient by doubling divisor until dividend < (tmp_divisor << 1). (line 22-27)

Reference: https://discuss.leetcode.com/topic/15568/detailed-explained-8ms-c-solution/2

 

Another idea is to use some mathematical properties to the quotient. If integer size is fixed at 32bit, then the algorithm takes constant time: https://discuss.leetcode.com/topic/17600/32-times-bit-shift-operation-in-c-with-o-1-solution