Watch 10 video solutions for Divide Two Integers, a medium level problem involving Math, Bit Manipulation. This walkthrough by take U forward has 223,426 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = 3.33333.. which is truncated to 3.
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 != 0Problem Overview: You are given two integers dividend and divisor. Compute the quotient without using multiplication, division, or modulus operators. The result must truncate toward zero and respect 32-bit signed integer limits.
Approach 1: Repeated Subtraction (O(n) time, O(1) space)
The most direct way to divide two numbers is to repeatedly subtract the divisor from the dividend until the remaining value becomes smaller than the divisor. Each subtraction represents one unit in the quotient. Track the number of successful subtractions and apply the correct sign at the end based on whether the inputs have the same sign.
This approach is easy to reason about and works well for small numbers. However, its runtime depends on the size of the quotient. In the worst case you subtract divisor from dividend roughly |dividend| / |divisor| times, which makes the time complexity O(n). It also requires careful handling of overflow when dividing INT_MIN by -1.
Approach 2: Bit Manipulation with Exponential Subtraction (O(log n) time, O(1) space)
A faster approach uses bit shifts to subtract large multiples of the divisor at once. Instead of subtracting the divisor one step at a time, repeatedly double it using left shifts (divisor << k) until it becomes just smaller than the current dividend. Subtract that value and add 2^k to the quotient.
This works because left shifting effectively multiplies the divisor by powers of two. Each iteration removes the largest possible chunk from the dividend, reducing the number of operations dramatically. The process resembles binary long division and relies heavily on bit manipulation and integer boundary handling.
To avoid overflow, convert numbers to long (or use 64-bit integers) during computation and clamp the final result within the 32-bit signed range. The sign of the result is determined using XOR logic on the signs of the inputs. This method runs in O(log n) time because each step reduces the dividend by powers of two.
Recommended for interviews: Interviewers expect the bit manipulation solution. The subtraction approach shows baseline understanding of division logic, but the optimized method demonstrates control over math reasoning and bitwise operations. Reaching the O(log n) solution signals strong algorithmic thinking and awareness of integer overflow edge cases.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Subtraction | O(n) | O(1) | Conceptual baseline or when numbers are very small |
| Bit Manipulation (Exponential Subtraction) | O(log n) | O(1) | Interview-expected optimized solution for large integers |