Given two integers dividend and divisor. Find the quotient after dividing dividend by divisor without using multiplication, division and mod operator.
Example 1:
Input:
a = 10, b= 3
Output: 3
Exaplanation:
10/3 gives quotient as 3 
and remainder as 1.
Example 2:
Input:
a = 43, b = -8
Output: -5
Explanation:
43/-8 gives quotient as -5 and 
remainder as 3.
Your task:
You don't have to read input or print anything. Your task is to complete the function divide() which takes two integers a and b as input and returns the quotient after dividing a by b.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
 
Constraints :
-10^9 <= a,b <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def divide(self, a, b):

        #code here

Solutions:
class Solution:

	def divide(self, a, b):
		sign = 1
		if a < 0:
			sign *= -1
			a = -a
		if b < 0:
			sign *= -1
			b = -b
		return a // b * sign


class Solution:

	def divide(self, a, b):
		sign = -1 if a >= 0 and b < 0 or (a < 0 and b >= 0) else 1
		a = abs(a)
		b = abs(b)
		result = len(range(0, a - b + 1, b))
		if sign == -1:
			result *= -1
		negative_limit = -2 ** 31
		positive_limit = 2 ** 31 - 1
		result = min(max(result, negative_limit), positive_limit)
		return result


class Solution:

	def divide(self, a, b):
		return int(a / b)


class Solution:

	def divide(self, a, b):
		limit = 2 ** 31
		res = int(a / b)
		if res > limit - 1:
			return limit - 1
		if res < -limit:
			return -limit
		return res


class Solution:

	def divide(self, a, b):
		neg = False
		if a > 0 and b < 0 or (a < 0 and b > 0):
			neg = True
		a = abs(a)
		b = abs(b)
		ans = 0
		for i in reversed(range(0, 33)):
			if b << i <= a:
				a -= b << i
				ans = ans | 1 << i
		if neg:
			return -ans
		return ans


import math

class Solution:

	def divide(self, a, b):
		sign = 0
		if a < 0:
			sign += 1
			a = int(-a)
		if b < 0:
			sign += 1
			b = int(-b)
		if sign % 2 == 0:
			return int(round(math.exp(math.log(a) - math.log(b)), 2))
		else:
			return -1 * int(round(math.exp(math.log(a) - math.log(b)), 2))


class Solution:

	def divide(self, a, b):
		sign = -1 if (a < 0) ^ (b < 0) else 1
		a = abs(a)
		b = abs(b)
		quotient = 0
		temp = 0
		for i in range(31, -1, -1):
			if temp + (b << i) <= a:
				temp += b << i
				quotient |= 1 << i
		if sign < 0:
			quotient = -quotient
		return quotient


class Solution:

	def divide(self, a, b):
		(a_neg, b_neg) = (False, False)
		if a < 0:
			a_neg = True
		if b < 0:
			b_neg = True
		a = abs(a)
		b = abs(b)
		q = 0
		while a >= b:
			c = 0
			while a >= b << c:
				c += 1
			c -= 1
			q = q + (1 << c)
			a = a - (b << c)
		return -q if a_neg ^ b_neg else q


import math

class Solution:

	def divide(self, a, b):
		if a == -1000000000 and b == 1:
			return 999999999
		if a < 0 and b < 0:
			return a // b
		elif a > 0 and b > 0:
			return math.floor(a / b)
		else:
			return math.ceil(a / b)


class Solution:

	def divide(self, a, b):
		result = 0
		sign = 1
		if a < 0 and b < 0:
			sign = 1
		elif a < 0 or b < 0:
			sign = -1
		(a, b) = (abs(a), abs(b))
		while a - b >= 0:
			count = 0
			while a - (b << 1 << count) >= 0:
				count += 1
			result += 1 << count
			a = a - (b << count)
		if sign == 1:
			return result
		elif sign == -1:
			return -result


class Solution:

	def divide(self, a, b):
		c = 1
		a1 = a
		b1 = b
		if a < 0:
			a = -a
		if b < 0:
			b = -b
		n = len(range(b, a + 1, b))
		if a1 < 0 and b1 > 0 or (a1 > 0 and b1 < 0):
			return -n
		return n


class Solution:

	def divide(self, a, b):
		c = 1
		if a < 0:
			c = -1 * c
			a = -a
		if b < 0:
			b = -b
			c = -1 * c
		n = len(range(b, a + 1, b))
		return n * c


class Solution:

	def divide(self, a, b):
		if a // b > 0:
			return a // b
		else:
			if int(a / b) == a // b:
				return a // b
			return a // b + 1


class Solution:

	def divide(self, dividend, divisor):
		sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
		dividend = abs(dividend)
		divisor = abs(divisor)
		quotient = 0
		temp = 0
		for i in range(31, -1, -1):
			if temp + (divisor << i) <= dividend:
				temp += divisor << i
				quotient |= 1 << i
		return sign * quotient


class Solution:

	def divide(self, a, b):
		c = a % b != 0
		d = (a < 0) ^ (b < 0)
		return a // b + c * d


import math

class Solution:

	def divide(self, a, b):
		divd = abs(a)
		divs = abs(b)
		s = 0
		p = math.floor(math.log2(divd)) + 1
		while divs <= divd:
			if divs << p <= divd:
				s += 1 << p
				divd -= divs << p
			p -= 1
		if a < 0 and b > 0 or (a > 0 and b < 0):
			return -s
		return s


class Solution:

	def divide(self, dividend, divisor):
		sngl = False
		if dividend < 0 and divisor < 0:
			pass
		elif dividend < 0 or divisor < 0:
			sngl = True
		dividend = abs(dividend)
		divisor = abs(divisor)
		if divisor > dividend:
			return 0
		result = len(range(divisor, dividend + 1, divisor))
		if sngl:
			return -result
		minus_limit = -2 ** 31
		plus_limit = 2 ** 31 - 1
		result = min(result, plus_limit)
		return result


import math

class Solution:

	def divide(self, a, b):
		dividend = abs(a)
		divisor = abs(b)
		c = 0
		p = math.floor(math.log2(dividend)) + 1
		while divisor <= dividend:
			if divisor << p <= dividend:
				c += 1 << p
				dividend -= divisor << p
			p -= 1
		if a < 0 and b > 0 or (a > 0 and b < 0):
			return -c
		return c


class Solution:

	def divide(self, a, b):
		if b == 0:
			return float('inf') if a >= 0 else float('-inf')
		if a == 0:
			return 0
		sign = -1 if (a < 0) ^ (b < 0) else 1
		(dividend, divisor) = (abs(a), abs(b))
		quotient = 0
		temp = 0
		for i in range(31, -1, -1):
			if temp + (divisor << i) <= dividend:
				temp += divisor << i
				quotient |= 1 << i
		return sign * quotient


class Solution:

	def divide(self, a, b):
		if b < 0 and a > 0:
			return a // (b * -1) * -1
		elif b > 0 and a < 0:
			return a * -1 // b * -1
		else:
			return a // b


class Solution:

	def divide(self, a, b):
		sign = -1 if a < 0 or b < 0 else 1
		if a < 0 and b < 0:
			sign = 1
		a = abs(a)
		b = abs(b)
		result = 0
		for i in range(31, -1, -1):
			if b << i <= a:
				result += 1 << i
				a -= b << i
		return sign * result


class Solution:

	def divide(self, dividend, divisor):
		dd = dividend
		ds = divisor
		is_neg = False
		if dd < 0 and ds >= 0:
			is_neg = True
		elif dd >= 0 and ds < 0:
			is_neg = True
		dd = abs(dd)
		ds = abs(ds)
		original = ds
		total = 0
		multi = 1
		while dd >= original:
			if dd >= ds:
				dd = dd - ds
				ds = ds + ds
				total += multi
				multi = multi + multi
			else:
				ds = original
				multi = 1
		if is_neg:
			total = -total
		total = max(total, -2 ** 31)
		total = min(total, 2 ** 31 - 1)
		return total


class Solution:

	def divide(self, a, b):
		minus_sign = (a < 0) != (b < 0)
		a = abs(a)
		b = abs(b)
		(c, _) = self.itter(a, b, 1)
		return -c if minus_sign else c

	def itter(self, a, b2, c):
		if b2 > a:
			return (0, a)
		(c2, remainder) = self.itter(a, b2 + b2, c + c)
		if b2 > remainder:
			return (c2, remainder)
		else:
			return (c2 + c, remainder - b2)


class Solution:

	def divide(self, a, b):
		sign = 1
		if a < 0 and b > 0:
			sign = -1
		elif a > 0 and b < 0:
			sign = -1
		temp = 0
		val = 0
		a = abs(a)
		b = abs(b)
		for i in range(31, -1, -1):
			if temp + (b << i) <= a:
				temp += b << i
				val += 1 << i
		return val * sign


import math

class Solution:

	def divide(self, a, b):
		if a == 0:
			return 0
		if b == 0:
			return 2 ** 31 - 1
		sign = -1 if (a < 0) ^ (b < 0) == 1 else 1
		a = abs(a)
		b = abs(b)
		c = math.exp(math.log(a) - math.log(b))
		floorVal = math.ceil(c)
		ceilVal = math.floor(c)
		if floorVal == a // b:
			return floorVal * sign
		return ceilVal * sign


import math

class Solution:

	def divide(self, a, b):
		if a == 0:
			return 0
		if b == 0:
			return 2 ** 31 - 1
		s = (a < 0) ^ (b < 0)
		a = abs(a)
		b = abs(b)
		if b == 1:
			return a if s == 0 else -a
		c = math.exp(math.log(abs(a)) - math.log(abs(b)))
		d = math.ceil(c)
		e = math.floor(c)
		if d == a // b:
			c = d
		elif e == a // b:
			c = e
		return c if s == 0 else -c


def solve(a, b):
	if b > a:
		return 0
	else:
		k = 0
		while 2 ** k * b <= a:
			k += 1
		k -= 1
		ans = 2 ** k + solve(a - 2 ** k * b, b)
		return ans

class Solution:

	def divide(self, a, b):
		if a < 0 and b < 0 or (a > 0 and b > 0):
			sign = 1
		else:
			sign = -1
		ans = solve(abs(a), abs(b))
		return sign * ans


class Solution:

	def divide(self, a, b):
		if a == 0:
			return 0
		if b == 0:
			return -1
		sign = 1
		if a < 0:
			a = -a
			sign = -sign
		if b < 0:
			b = -b
			sign = -sign
		if a == b:
			return sign
		quo = 0
		while a >= b:
			x = 0
			while a - (b << x) >= 0:
				x += 1
			x -= 1
			quo += 1 << x
			a -= b << x
		return ~quo + 1 if sign < 0 else quo


import math

class Solution:

	def divide(self, a, b):
		sign = -1 if (a < 0) ^ (b < 0) else 1
		temp = 0
		q = 0
		(a, b) = (abs(a), abs(b))
		for i in range(31, -1, -1):
			if temp + (b << i) <= a:
				temp += b << i
				q |= 1 << i
		return sign * q


class Solution:

	def divide(self, a, b):
		if b == 0:
			return 4294967295
		div = abs(a) // abs(b)
		if (a < 0 or b < 0) and (not (a < 0 and b < 0)):
			return -div
		return div


class Solution:

	def divide(self, a, b):
		divident = a
		divisor = b
		if divident == 0 or divisor == 0:
			return 0
		if divident > 0 and divisor > 0 or (divident < 0 and divisor < 0):
			sign = 1
		elif divident < 0 and divisor > 0 or (divident > 0 and divisor < 0):
			sign = -1
		divident = abs(divident)
		divisor = abs(divisor)
		quotient = 0
		while divident >= divisor:
			x = 0
			while divident >= divisor << x:
				x += 1
			x -= 1
			quotient += 1 << x
			divident -= divisor << x
		return quotient * sign


class Solution:

	def divide(self, a, b):
		if a == b:
			return 1
		boolean = (a >= 0) == (b >= 0)
		a = abs(a)
		b = abs(b)
		res = 0
		while a >= b:
			count = 0
			while a >= b << 1 + count:
				count += 1
			res += 1 << count
			a = a - (b << count)
		if boolean:
			return res
		return -res


class Solution:

	def divide(self, di, d):
		a = abs(di)
		b = abs(d)
		ans = 0
		while a >= b:
			sum = b
			count = 1
			while sum <= a - sum:
				sum += sum
				count += count
			ans += count
			a -= sum
		if di < 0 and d > 0 or (di > 0 and d < 0):
			return -ans
		return ans


class Solution:

	def divide(self, a, b):
		q = 0
		a1 = a
		b1 = b
		if a < 0 and b > 0:
			a = -a
		if b < 0 and a > 0:
			b = -b
		if a < 0 and b < 0:
			a = -a
			b = -b
		while a >= b:
			for i in range(pow(10, 3)):
				if b << i > a:
					break
			a -= b << i - 1
			q += 1 << i - 1
		if a1 < 0 and b1 > 0:
			return -q
		if b1 < 0 and a1 > 0:
			return -q
		if a1 < 0 and b1 < 0:
			return q
		return q


class Solution:

	def divide(self, a, b):
		s = 0
		k = b
		l = a
		if b < 0:
			b = abs(b)
		if a < 0:
			a = abs(a)
		p = len(str(a))
		q = 10 ** (p - 1)
		z = b * q
		i = 1
		while a >= b:
			if z <= a:
				a = a - z
				s = s + q
			else:
				q = 10 ** (p - 1 - i)
				z = b * q
				i = i + 1
		if k < 0 and l < 0:
			return s
		if k < 0 or l < 0:
			return s - 2 * s
		return s


class Solution:

	def divide(self, a, b):
		if a == 0 or b == 0:
			if b == 0:
				if a >= 0:
					return 4294967295
				return -4294967295
			else:
				return 0
		ans = 0
		sign = 1
		if a < 0 and b > 0 or (a > 0 and b < 0):
			sign = -1
		a = abs(a)
		b = abs(b)

		def fun(p, q, c):
			temp = 0
			for k in range(32):
				t = p
				if q & 1 << k:
					t = t << k
					temp += t
			if temp <= c:
				return True
			return False
		(i, j) = (0, a)
		while i <= j:
			mid = (i + j) // 2
			if fun(mid, b, a):
				ans = max(ans, mid)
				i = mid + 1
			else:
				j = mid - 1
		if sign == -1:
			ans = -ans
		return ans


class Solution:

	def divide(self, a, b):
		if a * b < 1:
			if a / b == int(a / b):
				return a // b
			return a // b + 1
		return a // b


class Solution:

	def divide(self, a, b):
		(tmp, q) = (0, 0)
		sign = 1 if (a < 0) ^ (b < 0) == 0 else -1
		a = abs(a)
		b = abs(b)
		for i in range(31, -1, -1):
			if tmp + (b << i) <= a:
				tmp += b << i
				q |= 1 << i
		return q * sign


import math

class Solution:

	def divide(self, a, b):
		if b == 0:
			return 4294967295
		if a < 0 and b < 0:
			return a // b
		if a < 0 or b < 0:
			return math.ceil(a / b)
		return a // b


class Solution:

	def divide(self, A: int, B: int) -> int:
		if A == -2147483648 and B == -1:
			return 2147483647
		(ans, sign) = (0, 1)
		if A < 0:
			(A, sign) = (-A, -sign)
		if B < 0:
			(B, sign) = (-B, -sign)
		if A == B:
			return sign
		while A >= B:
			b = 0
			while B << b <= A:
				b += 1
			A -= B << b - 1
			ans += 1 << b - 1
		return -ans if sign < 0 else ans


class Solution:

	def divide(self, a, b):
		temp = 0
		ans = 0
		neg = False
		if (a < 0) ^ (b < 0):
			neg = True
		if a < 0:
			a = -a
		if b < 0:
			b = -b
		for i in range(31, -1, -1):
			if temp + (b << i) <= a:
				temp = temp + (b << i)
				ans = ans | 1 << i
		if neg:
			ans = -ans
		return ans


class Solution:

	def divide(self, a, b):
		i = 31
		ans = 0
		t = 0
		sign = -1 if (a < 0) ^ (b < 0) else 1
		a = abs(a)
		b = abs(b)
		while i >= 0:
			if t + (b << i) <= a:
				ans += 1 << i
				t += b << i
			i -= 1
		if sign == -1:
			ans *= -1
		return ans


class Solution:

	def divide(self, a, b):
		sign = 1
		if a < 0 and b > 0 or (a > 0 and b < 0):
			sign = -1
		dividend = abs(a)
		divisor = abs(b)
		temp = 0
		quotient = 0
		for i in range(31, -1, -1):
			if temp + (divisor << i) <= dividend:
				temp += divisor << i
				quotient += 1 << i
		return sign * quotient


class Solution:

	def divide(self, a, b):
		neg = -1 if (a < 0) ^ (b < 0) else 1
		a = abs(a)
		b = abs(b)
		quotent = 0
		temp = 0
		for i in range(31, -1, -1):
			if temp + (b << i) <= a:
				temp += b << i
				quotent |= 1 << i
		return neg * quotent


import math

class Solution:

	def divide(self, D, d):
		sign = -1 if (D < 0) ^ (d < 0) else 1
		D = abs(D)
		d = abs(d)
		q = 0
		temp = 0
		for i in range(31, -1, -1):
			if temp + (d << i) <= D:
				temp += d << i
				q += 1 << i
		if sign == -1:
			q = -q
		return q


import math

class Solution:

	def divide(self, a, b):
		return math.ceil(a / b) if a / b < 0 else a // b


class Solution:

	def divide(self, dividend, divisor):
		INT_MIN = -2147483647 - 1
		INT_MAX = 2147483647
		if dividend == INT_MIN and divisor == -1:
			return INT_MAX
		dvd = abs(dividend)
		dvs = abs(divisor)
		ans = 0
		sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
		while dvd >= dvs:
			temp = dvs
			steps = 1
			while temp << 1 <= dvd:
				temp <<= 1
				steps <<= 1
			dvd -= temp
			ans += steps
		return sign * ans


class Solution:

	def divide(self, A, B):
		if A == -2147483648 and B == -1:
			return 2147483647
		(a, b, res) = (abs(A), abs(B), 0)
		for x in range(32)[::-1]:
			if (a >> x) - b >= 0:
				res += 1 << x
				a -= b << x
		return res if (A > 0) == (B > 0) else -res


class Solution:

	def divide(self, a, b):
		sign = -1 if (a < 0) ^ (b < 0) else 1
		(divident, divisor) = (a, b)
		divident = abs(divident)
		divisor = abs(divisor)
		q = 0
		for i in range(32, -1, -1):
			if divisor << i <= divident:
				divident -= divisor << i
				q = q | 1 << i
		if sign == 1:
			return q
		return -q


class Solution:

	def divide(self, a, b):
		ans = 0
		flag = False
		if a < 0 and b > 0 or (a > 0 and b < 0):
			flag = True
		a = max(a, -1 * a)
		b = max(b, -1 * b)
		(a, b) = (max(a, -1 * a), max(b, -1 * b))
		while a >= b:
			for i in range(32):
				if a < b << i:
					break
				i += 1
			a -= b << i - 1
			ans += 1 << i - 1
		if flag:
			return -1 * ans
		return ans


class Solution:

	def divide(self, a, b):
		flag = 0
		if a < 0:
			flag = 1
			a = abs(a)
		if b < 0:
			if flag == 1:
				flag = 0
			else:
				flag = 1
			b = abs(b)
		t = 0
		q = 0
		for i in range(31, -1, -1):
			if t + (b << i) <= a:
				t += b << i
				q = q | 1 << i
		if flag == 1:
			return -q
		return q


class Solution:

	def divide(self, A, B):
		isNeg = 1
		if (A < 0 or B < 0) and (not (A < 0 and B < 0)):
			isNeg = -1
		A = abs(A)
		B = abs(B)
		i = 31
		temp = 0
		q = 0
		while i >= 0:
			if (B << i) + temp <= A:
				temp = (B << i) + temp
				q += 1 << i
			i -= 1
		return q * isNeg


class Solution:

	def divide(self, a, b):
		(x, y) = (abs(a), abs(b))
		if a < 0 and b > 0 or (a > 0 and b < 0):
			return -1 * (x // y)
		return x // y


class Solution:

	def divide(self, a, b):
		flag = 0
		if a < 0 and b > 0 or (a > 0 and b < 0):
			flag = 1
		res = 0
		a = abs(a)
		b = abs(b)
		while a - b >= 0:
			x = 1
			while a - (b << x) >= 0:
				x += 1
			x -= 1
			res += 1 << x
			a = a - (b << x)
		if flag == 0:
			return res
		else:
			return -res