Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:


Input: dividend = 10, divisor = 3
Output: 3

Example 2:


Input: dividend = 7, divisor = -3
Output: -2

Note:


       Both dividend and divisor will be 32-bit signed integers.
       The divisor will never be 0.
       Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

Difficulty: interview

Starter code:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        

Solutions:
class Solution:
     def get_half(self,dividend,divisor):
         abs_dividend = abs(dividend)
         abs_divisor = abs(divisor)
         num = divisor
         num_temp=0
         result=1
         result_temp=0
         while (num<=dividend):
             num_temp=num
             num+=num
             result_temp=result
             result+=result
         return num_temp,result_temp
 
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         MAX_INT = 2147483647
         if divisor == 0:
             return MAX_INT
         abs_dividend = abs(dividend)
         abs_divisor = abs(divisor)
         if abs_dividend <abs_divisor:
             return 0
         minus_flag = (dividend is abs_dividend) is (divisor is abs_divisor)
         final_result=0
         while(abs_dividend>=abs_divisor):
             num,result=self.get_half(abs_dividend,abs_divisor)
             abs_dividend-=num
             final_result+=result
 
         if minus_flag==1:
             if final_result>MAX_INT:
                 return MAX_INT
             return final_result
         else:
             if 0-final_result<0-MAX_INT-1:
                 return 0-MAX_INT
             return 0-final_result

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         positive = (dividend < 0) is (divisor < 0)
         dividend, divisor = abs(dividend), abs(divisor)
         res = 0
         while dividend >= divisor:
             temp, i = divisor, 1
             while dividend >= temp:
                 dividend -= temp
                 res += i
                 temp <<= 1
                 i <<= 1
         if not positive:
             res = -res
         return min(max(-2147483648, res), 2147483647)

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         if abs(dividend) < abs(divisor):
             return 0
         sum, count, result = 0, 0, 0
         a, b = abs(dividend), abs(divisor)
         while a >= b:
             sum = b
             count = 1
             while sum+sum < a:
                 sum += sum
                 count += count
             a -= sum
             result += count
         if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
             result = 0-result
         return min(result,2147483647)
         


class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         MIN_INT = -2**31
         MAX_INT = -MIN_INT - 1
         if divisor == 0 or (dividend == MIN_INT and divisor==-1):
             return MAX_INT
         sign = 1
         if dividend < 0:
             sign = -sign
             dividend = -dividend
         if divisor < 0:
             sign = -sign
             divisor = -divisor
         ans = bits = 0
         while (divisor<<(bits+1)) <= dividend:
             bits += 1
         while bits >= 0:
             if dividend >= (divisor<<bits):
                 dividend -= (divisor<<bits)
                 ans += (1<<bits)
             bits -= 1
         return ans if sign==1 else -ans

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         positive = (dividend < 0) is (divisor < 0)
         dividend, divisor, div = abs(dividend), abs(divisor), abs(divisor)
         res = 0
         q = 1
         while dividend >= divisor:
                 dividend -= div
                 res += q
                 q += q
                 div += div
                 if dividend < div:
                     div = divisor
                     q = 1
         if not positive:
             res = -res
         return min(max(-2147483648, res), 2147483647)

class Solution:
 # @return an integer
     def divide(self, dividend, divisor):
         positive = (dividend < 0) is (divisor < 0)
         dividend, divisor = abs(dividend), abs(divisor)
         res = 0
         while dividend >= divisor:
             temp, i = divisor, 1
             while dividend >= temp:
                 dividend -= temp
                 res += i
                 i <<= 1
                 temp <<= 1
         if not positive:
             res = -res
         return min(max(-2147483648, res), 2147483647)

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         tag = 1 if (dividend < 0) is (divisor < 0) else -1
         dividend, divisor = abs(dividend), abs(divisor)
         if divisor == 0:
             return float('inf')
         count = 0
         
         while dividend >= divisor:
             mul = 1
             t = divisor
             while dividend > (t<<1):
                 t <<= 1
                 mul <<= 1
             dividend -= t
             count += mul
             #print(dividend, mul)
         return min(max(-2147483648, count*tag), 2147483647)

class Solution:
     import sys
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         maxint = 2**31 - 1
         minint = -2**31
         sign = (2*(dividend>0) - 1) * (2*(divisor>0) - 1)
         quotient = 0
         dividend *= (2*(dividend>0) - 1)
         divisor *= (2*(divisor>0) - 1)
         remainder = dividend
         for i in reversed(list(range(32))):
             if remainder == 0: break
             if divisor << i <= remainder:
                 remainder -= divisor << i
                 quotient += 1 << i
         quotient *= sign
         print(quotient)
         if quotient > maxint or quotient < minint:  quotient = maxint
         return quotient

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
             if abs(dividend) < abs(divisor):
                 return 0
         summ = 0; count = 0; res = 0
         a = abs(dividend); b = abs(divisor)
         while a >= b:
             summ = b
             count = 1
             while summ + summ <= a:
                 summ += summ
                 count += count
             a -= summ
             res += count
         if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
                 res = 0 - res
         if res > 2**31 - 1:
                 res = 2**31 - 1
         return res


class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         
         flag = (dividend < 0) is (divisor < 0)
         dividend, divisor = abs(dividend), abs(divisor)        
         result = 0
         while dividend >= divisor:
             newDivisor, rate = divisor, 1
             while dividend >= newDivisor:
                 dividend -= newDivisor
                 result += rate
                 newDivisor <<= 1
                 rate <<= 1
         if not flag:
             result = 0 - result       
         return min(max(-2147483648, result), 2147483647)

class Solution:
     def divide(self, dividend, divisor):
         positive = (dividend < 0) is (divisor < 0)
         dividend, divisor = abs(dividend), abs(divisor)
         res = 0
         while dividend >= divisor:
             temp, i = divisor, 1
             while dividend >= temp:
                 dividend -= temp
                 res += i
                 i <<= 1
                 temp <<= 1
         if not positive:
             res = -res
         return min(max(-2147483648, res), 2147483647)

class Solution:
     def divide(self, dividend, divisor):
         """
         :type dividend: int
         :type divisor: int
         :rtype: int
         """
         
         flag = (dividend < 0) is (divisor < 0)
         dividend, divisor = abs(dividend), abs(divisor)        
         result = 0
         while dividend >= divisor:
             newDivisor, rate = divisor, 1
             while dividend >= newDivisor:
                 dividend -= newDivisor
                 result += rate
                 newDivisor <<= 1
                 rate <<= 1
         if not flag:
             result = 0 - result       
         return min(max(-2147483648, result), 2147483647)