29. Divide Two Integers
Medium
Description
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.
Return the quotient after dividing dividend by divisor.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.
Example 1:
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
-231<= dividend, divisor <= 231- 1divisor != 0
Solutions
Video Solution Coming Soon
Approach: Simulation
Time complexity: \(O(log \times n)\)
Space complexity: \(O(1)\)
Way 1
Algorithmic Way
The time complexity of the algorithm is \(O(log \times n)\) where n is the value of the dividend. This is because we use bit shifting to reduce the size of the dividend logarithmically.
The space complexity of the algorithm is \(O(1)\). We use a fixed amount of extra space for variables regardless of the input size.
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
# Handle overflow case
if dividend == -2**31 and divisor == -1:
return 2**31 - 1
# Determine the sign of the result
sign = (dividend < 0) != (divisor < 0)
# Work with positive values for simplicity
dvd, dvs = abs(dividend), abs(divisor)
ans = 0 #quotient
hs = 31 # The highest bit for divisor to be shifted
# Find the highest bit where divisor can be shifted
while hs >= 0 and (dvs << hs) > dvd:
hs -= 1
# Subtract shifted divisor from dividend
for i in range(hs, -1, -1):
if (dvs << i) <= dvd:
dvd -= (dvs << i)
ans += (1 << i)
# Apply the sign to the quotient
return -ans if sign else ans
Bitwise Left Shift operator <<
In Python, a << b is read as "a left-shifted by b bits." It's a bitwise operator that shifts the binary representation of a to the left by b positions. This is equivalent to multiplying a by 2 raised to the power of b (i.e., a * 2**b). Zeroes are filled in from the right during the shift.
Access to detailed solutions requires a login. Already have an account? Don't have an account yet?
👋 Please log in to view the solution
Akhil Singh Chauhan
Author