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 <limits.h>
2
3int divide(int dividend, int divisor) {
4 if (divisor == 0) return INT_MAX;
5The C code starts by checking for division by zero or the special overflow case where the dividend is INT_MIN and the divisor is -1. It calculates the result's sign based on the input signs.
Using long long for the absolute values ensures no overflow. While the dividend is greater than or equal to the divisor, it deducts the divisor from the dividend and increments the quotient.
Finally, it applies the sign to the quotient and returns the result.
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
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).
This C solution utilizes bit shifting to match divisor powers of 2 and left shifts while deducting divisor multiplicities from the dividend. It results in a multistage process of merging high bits calculation primarily through shift comparisons between divisor equivalences.