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 != 0The key challenge in #29 Divide Two Integers is performing integer division without using multiplication, division, or modulo operators. A brute-force approach would repeatedly subtract the divisor from the dividend, but this leads to poor performance for large values.
A more efficient strategy uses bit manipulation. The idea is to repeatedly double the divisor using left shifts (<<) until it becomes just smaller than or equal to the dividend. This allows you to subtract large multiples of the divisor in a single step, similar to how long division works. By tracking how many times the shifted divisor fits into the dividend, you can accumulate the quotient efficiently.
Carefully handle edge cases such as negative numbers, overflow (especially when dividing INT_MIN by -1), and sign determination. Using bit shifting reduces the number of operations significantly, leading to a logarithmic-time solution.
This optimized method achieves O(log n) time complexity with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Repeated subtraction | O(n) | O(1) |
| Bit manipulation with shifting | O(log n) | O(1) |
NeetCode
This approach uses repeated subtraction to calculate the quotient. The idea is to keep subtracting the divisor from the dividend until the dividend
Time Complexity: O(n), where n is the result of the division. This can be inefficient for large numbers.
Space Complexity: O(1), as no extra space is used.
1function divide(dividend, divisor) {
2 if (divisor === 0) return Number.MAX_SAFE_INTEGER;
3 if (dividend === -(2JavaScript's version calculates division similar to C-like approaches, checking for divisor zero, handling overflows, and using bitwise XOR for sign assessment. It uses a while loop to decrement the dividend while tracking how many times subtraction occurs until input conditions are satisfied.
Bit manipulation provides an optimized method to divide without causing repeated subtractions. By efficiently finding how many times the divisor can be shifted left (multiplied by two) in the dividend range, we can ascertain parts of the quotient to sum incrementally. This halves the number of operations compared to repeated subtraction.
Time Complexity: O(log n), where n is the approximate number of bits in the dividend with respect to bit manipulation.
Space Complexity: O(1), as shifts occur without additional structures.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in technical interviews at companies like FAANG. It tests understanding of bit manipulation, edge case handling, and implementing arithmetic logic without built-in operators.
This problem does not require complex data structures. It mainly relies on integer arithmetic and bit manipulation operations like left shift to efficiently compute the quotient.
Bit manipulation allows you to double numbers quickly using left shifts, which helps subtract large multiples of the divisor at once. This significantly reduces the number of operations compared to repeated subtraction.
The optimal approach uses bit manipulation. By repeatedly left-shifting the divisor and subtracting the largest possible multiple from the dividend, you simulate long division efficiently. This reduces the complexity to O(log n).
Java's bit manipulation method effectively uses long values with logical bit shifting operations. It starts with bit position examination decrement-wise, and successive confirmations allow the right subtraction of pre-multiplied equivalents.