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: Divide two integers without using multiplication, division, or modulo operators. Return the quotient after dividing dividend by divisor. The tricky part is handling negative numbers, overflow, and making the algorithm efficient enough to avoid repeated subtraction for large inputs.
Approach 1: Repeated Subtraction (O(n) time, O(1) space)
The most straightforward strategy repeatedly subtracts the divisor from the dividend until the remaining value becomes smaller than the divisor. Each subtraction represents one unit in the quotient. You first normalize the sign of both numbers using absolute values, track whether the result should be negative, and keep subtracting in a loop while counting operations.
This approach is easy to implement and clearly demonstrates the mechanics of division. However, its performance degrades quickly when the dividend is large because it performs one subtraction per unit of quotient. For example, dividing 1,000,000 by 1 requires one million iterations. Time complexity is O(n) where n = dividend / divisor, and space complexity is O(1). This method mainly helps illustrate the problem before optimizing it.
Approach 2: Bit Manipulation with Exponential Subtraction (O(log n) time, O(1) space)
The optimized solution uses bit manipulation to speed up subtraction. Instead of subtracting the divisor one step at a time, double it repeatedly using left shifts (divisor << k) until it becomes just smaller than the remaining dividend. This effectively subtracts large multiples of the divisor in a single step.
Each shift represents multiplying the divisor by powers of two. When a shifted value fits inside the remaining dividend, subtract it and add the corresponding power of two to the quotient. Continue reducing the dividend while scanning shifts from large to small. This mirrors how long division works but implemented with binary operations.
Handling overflow is critical. The edge case dividend = -2^31 and divisor = -1 exceeds the 32-bit signed integer range, so the result must be clamped to 2^31 - 1. After determining the final sign, return the computed quotient. Because the divisor doubles each step, the number of iterations is bounded by the bit length of the integer, giving O(log n) time and O(1) extra space. The method relies on binary shifts and arithmetic reasoning from math and bit-level operations.
Recommended for interviews: Interviewers expect the bit manipulation solution. The subtraction method demonstrates you understand the division process but does not scale. The exponential subtraction technique shows algorithmic optimization and comfort with binary operations, which is exactly what this problem is designed to test.
This approach uses repeated subtraction to calculate the quotient. The idea is to keep subtracting the divisor from the dividend until the dividend
The 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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach 1: Subtraction-based | 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. |
| Approach 2: Bit Manipulation | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Subtraction | O(n) | O(1) | Understanding the basic concept of division or explaining the brute force logic first in interviews |
| Bit Manipulation (Exponential Subtraction) | O(log n) | O(1) | Optimal approach for large integers and the expected interview solution |
Sum of Two Integers - Leetcode 371 - Java • NeetCode • 144,288 views views
Watch 9 more video solutions →Practice Divide Two Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor