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.
1#include <climits>
2
3int divide(int dividend, int divisor) {
4 if (divisor == 0) return INT_MAX;
5 if (dividend == INT_MIN && divisor == -1) return INT_MAX;
6 int sign = ((dividend < 0) ^ (divisor < 0)) ? -1: 1;
7 long long ldividend = abs((long long)dividend);
8 long long ldivisor = abs((long long)divisor);
9 int quotient = 0;
10 while (ldividend >= ldivisor) {
11 ldividend -= ldivisor;
12 ++quotient;
13 }
return sign * quotient;
}The C++ solution follows the same logic as the C implementation. It utilizes the long long type for the dividend and divisor to prevent overflow issues when converting to absolute values. The loop continually subtracts the divisor from the larger dividend countingly till the dividend is smaller than the divisor and then returns the correctly signed quotient.
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.
1 public int Divide(int dividend, int divisor) {
if (divisor == 0) return int.MaxValue;
if (dividend == int.MinValue && divisor == -1) return int.MaxValue;
long ldividend = Math.Abs((long)dividend);
long ldivisor = Math.Abs((long)divisor);
int result = 0;
for (int i = 31; i >= 0; i--) {
if ((ldividend >> i) >= ldivisor) {
ldividend -= (ldivisor << i);
result += (1 << i);
}
}
return ((dividend < 0) ^ (divisor < 0)) ? -result : result;
}
}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).
C# implementation requires using Math.Abs() and long types due to language headroom limitations while computing division equivalents without direct fractional comparison. Bit operations gradually develop quotient parts based on power division within permissible value calculations.