Divide Two Integers solution and explanation
Google
9 more videos on this problem
L9. Divide Two Integers without using Multiplication and Division Operators | Bit Manipulationtake U forward · 19:12 · 249K views
Divide Two Integers | Leetcode - 29Algorithms Made Easy · 10:30 · 74K views
Leetcode 29 - Bit Manipulation | Divide Two IntegersNideesh Terapalli · 9:32 · 64K views
Leetcode - Divide Two Integers (Python)Timothy H Chang · 6:19 · 19K views
Leetcode 29 Divide two integers | Very Easy Explanation | HindiThinkCode · 7:10 · 17K views
Divide Two Integer (LeetCode 29) | Without the use of multiply and division operator | BitwiseNikhil Lohia · 17:05 · 4K views
[English] LeetCode 29. Divide Two Integershappygirlzt · 9:54 · 3K views
Divide Two Integers Python Solution - LeetCode #29Professor Oakes · 9:10 · 3K views
LeetCode: 29. Divide Two Integers (Visualized)Code With Zi · 20:59 · 2K views
leetCode 29 - Divide Two IntegersJSer · 19:59 · 1K views
The problem
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
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if divisor == 0:
return 2**31 - 1
if dividend == -2**31 and divisor == -1:
return 2**31 - 1
sign = -1 if (dividend < 0) != (divisor < 0) else 1
dividend, divisor = abs(dividend), abs(divisor)
quotient = 0
while dividend >= divisor:
dividend -= divisor
quotient += 1
return sign * quotientpublic class Divider {
public int divide(int dividend, int divisor) {
if (divisor == 0) return Integer.MAX_VALUE;
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
int quotient = 0;
while (ldividend >= ldivisor) {
ldividend -= ldivisor;
quotient++;
}
return sign * quotient;
}
}#include <climits>
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1: 1;
long long ldividend = abs((long long)dividend);
long long ldivisor = abs((long long)divisor);
int quotient = 0;
while (ldividend >= ldivisor) {
ldividend -= ldivisor;
++quotient;
}
return sign * quotient;
}function divide(dividend, divisor) {
if (divisor === 0) return Number.MAX_SAFE_INTEGER;
if (dividend === -(2**31) && divisor === -1) return (2**31) - 1;
var sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
var ldividend = Math.abs(dividend);
var ldivisor = Math.abs(divisor);
var quotient = 0;
while (ldividend >= ldivisor) {
ldividend -= ldivisor;
quotient++;
}
return sign * quotient;
}#include <limits.h>
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long long ldividend = llabs((long long)dividend);
long long ldivisor = llabs((long long)divisor);
int quotient = 0;
while (ldividend >= ldivisor) {
ldividend -= ldivisor;
++quotient;
}
return sign * quotient;
}public class Solution {
public int Divide(int dividend, int divisor) {
if (divisor == 0) return int.MaxValue;
if (dividend == int.MinValue && divisor == -1) return int.MaxValue;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long ldividend = Math.Abs((long)dividend);
long ldivisor = Math.Abs((long)divisor);
int quotient = 0;
while (ldividend >= ldivisor) {
ldividend -= ldivisor;
quotient++;
}
return sign * quotient;
}
}Python's solution employs a class-based implementation, handling edge cases up front. Signs are assessed using tuple unpacking and conditional logic.
Computations use while loops to repeatedly subtract the divisor from the dividend and incrementally add to the quotient until the dividend is less than the divisor.
Time Complexity: O(n), similar to previous implementations due to iterative subtraction.
Space Complexity: O(1), as the space usage is constant aside from function call overhead.
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.
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if divisor == 0:
return 2**31 - 1
if dividend == -2**31 and divisor == -1:
return 2**31 - 1
sign = -1 if (dividend < 0) != (divisor < 0) else 1
dividend, divisor = abs(dividend), abs(divisor)
quotient = 0
for i in range(31, -1, -1):
if (dividend >> i) >= divisor:
dividend -= divisor << i
quotient += 1 << i
return sign * quotientpublic class Divider {
public int divide(int dividend, int divisor) {
if (divisor == 0) return Integer.MAX_VALUE;
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
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;
}
}#include <climits>
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
long long ldividend = std::abs((long long) dividend);
long long ldivisor = std::abs((long 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;
}function divide(dividend, divisor) {
if (divisor === 0) return Number.MAX_SAFE_INTEGER;
if (dividend === -(2**31) && divisor === -1) return (2**31) - 1;
var sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
var ldividend = Math.abs(dividend);
var ldivisor = Math.abs(divisor);
var quotient = 0;
for (var i = 31; i >= 0; i--) {
if ((ldividend >> i) >= ldivisor) {
ldividend -= (ldivisor << i);
quotient += 1 << i;
}
}
return sign * quotient;
}#include <limits.h>
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
long long ldividend = llabs((long long)dividend);
long long ldivisor = llabs((long 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;
}public class Solution {
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;
}
}Using an extensive logical bit evaluation per shift comparison, Python methodically manages bit examination to reduce dividend using viable divisor strengths. The technique achieves efficient quotient identification by summing constants against shifted checks typically.
Time Complexity: O(log n), results effects reflect bitwise evaluation and iteration through shifts for matching combinations.
Space Complexity: O(1), utilizing few temporary variables beyond dedicated plan operations.
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).
function divide(a: number, b: number): number {
if (b === 1) {
return a;
}
if (a === -(2 ** 31) && b === -1) {
return 2 ** 31 - 1;
}
const sign: boolean = (a > 0 && b > 0) || (a < 0 && b < 0);
a = a > 0 ? -a : a;
b = b > 0 ? -b : b;
let ans: number = 0;
while (a <= b) {
let x: number = b;
let cnt: number = 1;
while (x >= -(2 ** 30) && a <= x << 1) {
x <<= 1;
cnt <<= 1;
}
ans += cnt;
a -= x;
}
return sign ? ans : -ans;
}func divide(a int, b int) int {
if b == 1 {
return a
}
if a == math.MinInt32 && b == -1 {
return math.MaxInt32
}
sign := (a > 0 && b > 0) || (a < 0 && b < 0)
if a > 0 {
a = -a
}
if b > 0 {
b = -b
}
ans := 0
for a <= b {
x := b
cnt := 1
for x >= (math.MinInt32>>1) && a <= (x<<1) {
x <<= 1
cnt <<= 1
}
ans += cnt
a -= x
}
if sign {
return ans
}
return -ans
}class Solution {
/**
* @param integer $a
* @param integer $b
* @return integer
*/
function divide($a, $b) {
if ($b == 0) {
throw new Exception('Can not divide by 0');
} elseif ($a == 0) {
return 0;
}
if ($a == -2147483648 && $b == -1) {
return 2147483647;
}
$sign = $a < 0 != $b < 0;
$a = abs($a);
$b = abs($b);
$ans = 0;
while ($a >= $b) {
$x = $b;
$cnt = 1;
while ($a >= $x << 1) {
$x <<= 1;
$cnt <<= 1;
}
$a -= $x;
$ans += $cnt;
}
return $sign ? -$ans : $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Subtraction-based | Time Complexity: O(n), similar to previous implementations due to iterative subtraction. Space Complexity: O(1), as the space usage is constant aside from function call overhead. |
| Approach 2: Bit Manipulation | Time Complexity: O(log n), results effects reflect bitwise evaluation and iteration through shifts for matching combinations. Space Complexity: O(1), utilizing few temporary variables beyond dedicated plan operations. |
| Simulation + Fast Power | – |
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 |
Frequently asked questions
Is Divide Two Integers easy or hard?
Divide Two Integers is generally considered a medium-level problem. The challenge comes from implementing division without using multiplication, division, or modulus operators while correctly handling negative numbers and 32-bit integer overflow.
Divide Two Integers Python/Java solution
Python and Java implementations usually convert values to long (or use Python's large integers) to safely handle overflow during calculations. The algorithm then applies bit shifting to subtract powers of two multiples of the divisor until the quotient is determined.
How to solve Divide Two Integers in O(log n)?
Use bit manipulation to repeatedly double the divisor with left shifts until it is just less than or equal to the remaining dividend. Subtract that value and add the corresponding power of two to the quotient. Continue until the dividend becomes smaller than the divisor. This mimics binary long division and runs in O(log n).
What is the best approach for Divide Two Integers?
The best approach uses bit manipulation with exponential subtraction. Instead of subtracting the divisor one step at a time, the algorithm repeatedly doubles the divisor using left shifts and subtracts the largest valid multiple. This reduces the runtime to O(log n) while using constant extra space.
Is Divide Two Integers asked at Google/Amazon/Meta?
Divide Two Integers frequently appears in interviews at large tech companies because it tests integer arithmetic, overflow handling, and bit manipulation. Variants of the problem have been reported in interviews at Amazon, Google, and Meta for software engineering roles.
What data structure is used in Divide Two Integers?
No complex data structure is required. The problem relies mainly on arithmetic operations and bit manipulation. Variables track the dividend, divisor, shifted multiples, and the accumulated quotient.
What is the time complexity of Divide Two Integers?
The optimal solution runs in O(log n) time because the divisor is doubled using bit shifts and subtracted in powers of two. The basic subtraction approach runs in O(n) time where n is roughly |dividend| / |divisor|. Both methods use O(1) auxiliary space.