Divide Two Integers - Solution & Explanation
Problem Statement
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 != 0
Approach Overview
Problem 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 1: Approach 1: Subtraction-based
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.
Complexity
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: Approach 2: Bit Manipulation
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.
Complexity
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 3: Simulation + Fast Power
Division is essentially subtraction. The problem requires us to calculate the integer result after dividing two numbers, which is actually calculating how many divisors and a number less than the divisor constitute the dividend. However, only one subtraction can be done in one loop, which is too inefficient and will lead to timeout. This can be optimized by using the idea of fast power.
It should be noted that since the problem explicitly requires that only 32-bit signed integers can be used at most, the divisor and dividend need to be converted to negative numbers for calculation. Because converting to positive numbers may cause overflow, such as when the dividend is INT32_MIN, it will be greater than INT32_MAX when converted to a positive number.
Assuming the dividend is a and the divisor is b, the time complexity is O(log a times log b), and the space complexity is O(1).
Complexity Comparison
| 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. |
| Simulation + Fast Power | — |
Detailed Complexity Analysis
| 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 |
Video Solution
L9. Divide Two Integers without using Multiplication and Division Operators | Bit Manipulation • take U forward • 249,238 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Divide Two Integers easy or hard?
Divide Two Integers Python/Java solution
How to solve Divide Two Integers in O(log n)?
What is the best approach for Divide Two Integers?
Is Divide Two Integers asked at Google/Amazon/Meta?
What data structure is used in Divide Two Integers?
What is the time complexity of Divide Two Integers?
Ready to solve this problem?
Practice Divide Two Integers with our built-in code editor and test cases.
Practice on FleetCode