Log inSign up
mediumLeetCodeNot Started

Divide Two Integers Without Operators

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given two integers dividend and divisor, divide two integers without using multiplication, division, and the mod operator.

The integer division should truncate toward zero, which means losing its fractional parts (e.g., 8.345 truncates to 8, and -2.7335 truncates to -2).

Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [-2^31, 2^31 - 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, return 2^31 - 1, and if the quotient is strictly less than -2^31, return -2^31.

Example 1 · Example 1: Positive Division:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10 / 3 = 3.33333..., which truncates to 3.

Example 2 · Example 2: Negative Division:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7 / -3 = -2.33333..., which truncates to -2.

Example 3 · Example 3: Overflow Edge Case:

Input: dividend = -2147483648, divisor = -1
Output: 2147483647
Explanation: -2147483648 / -1 = 2147483648, which exceeds 32-bit signed INT_MAX (2147483647). Clamped to 2147483647.

Constraints:

  • -231 <= dividend, divisor <= 231 - 1
  • divisor != 0

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Simulate division using powers of two through bit shifts.
  • Identify and guard against INT_MIN (-2147483648) negation overflow.
  • Master bitwise long division patterns applicable to arbitrary precision arithmetic.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Division requested without using /, *, or %.
  • 32-bit integer boundary constraints.
  • Simulating arithmetic operations with bit-level logic.

Algorithmic Decision Tree:

  • Handle INT_MIN / -1 overflow upfront.
  • Determine sign of quotient: (dividend < 0) ^ (divisor < 0).
  • Iterate i from 31 down to 0, subtracting (divisor << i) whenever dividend >= (divisor << i).

Connected Patterns:

Bitwise AND of Numbers RangeSquare of a Number Without MultiplicationSum of Two Integers

1. Repeated Subtraction

Intuition

Determine the sign. Convert both numbers to positive absolute values. While dividend >= divisor, subtract divisor and increment quotient. Apply sign and check overflow limits.

When to apply: Conceptual explanation of division as repeated subtraction.

Algorithm

  1. Step 1: Guard against INT_MIN / -1 overflow.
  2. Step 2: Determine sign: negative if (dividend < 0) ^ (divisor < 0).
  3. Step 3: Loop while absDividend >= absDivisor: absDividend -= absDivisor, count++.
  4. Step 4: Return sign ? -count : count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <cmath>
4
5using namespace std;
6
7int divideBrute(int dividend, int divisor) {
8 if (dividend == INT_MIN && divisor == -1) return INT_MAX;
9 bool isNeg = (dividend < 0) ^ (divisor < 0);
10 long long a = abs((long long)dividend);
11 long long b = abs((long long)divisor);
12 long long count = 0;
13 while (a >= b) {
14 a -= b;
15 count++;
16 }
17 return isNeg ? (int)-count : (int)count;
18}
19
20int main() {
21 cout << "Brute (10, 3): " << divideBrute(10, 3) << endl; // 3
22 cout << "Brute (7, -3): " << divideBrute(7, -3) << endl; // -2
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(dividend / divisor)
  • Space complexity: O(1)

2. Exponential Doubling

Intuition

While dividend >= divisor, find the largest multiple temp = divisor * 2^k that fits into dividend. Subtract temp from dividend and add 2^k to the quotient. Repeat until dividend < divisor.

When to apply: When understanding how powers of two accelerate division.

Algorithm

  1. Step 1: Check overflow edge case.
  2. Step 2: Determine sign and convert to 64-bit absolute values.
  3. Step 3: Outer loop while a >= b.
  4. Step 4: Inner loop: double temp = b and multiple = 1 while a >= (temp << 1).
  5. Step 5: a -= temp, quotient += multiple.
  6. Step 6: Return signed clamped quotient.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <cmath>
4
5using namespace std;
6
7int divideDoubling(int dividend, int divisor) {
8 if (dividend == INT_MIN && divisor == -1) return INT_MAX;
9 bool isNeg = (dividend < 0) ^ (divisor < 0);
10 long long a = abs((long long)dividend);
11 long long b = abs((long long)divisor);
12 long long quotient = 0;
13
14 while (a >= b) {
15 long long temp = b;
16 long long multiple = 1;
17 while (a >= (temp << 1)) {
18 temp <<= 1;
19 multiple <<= 1;
20 }
21 a -= temp;
22 quotient += multiple;
23 }
24
25 long long res = isNeg ? -quotient : quotient;
26 if (res > INT_MAX) return INT_MAX;
27 if (res < INT_MIN) return INT_MIN;
28 return (int)res;
29}
30
31int main() {
32 cout << "Doubling (10, 3): " << divideDoubling(10, 3) << endl; // 3
33 cout << "Doubling (7, -3): " << divideDoubling(7, -3) << endl; // -2
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O((log n)^2)
  • Space complexity: O(1)

3. Bitwise Long Division (31 down to 0)

Intuition

Iterate i from 31 down to 0. If a >= (b << i), we know that 2^i multiples of b fit into a. We subtract b << i from a and activate bit i in quotient (quotient |= (1LL << i)). This performs exactly 32 bit-shift comparisons.

When to apply: Optimal canonical solution for 32-bit division without operators.

Algorithm

  1. Step 1: Handle overflow: if dividend == INT_MIN and divisor == -1, return INT_MAX.
  2. Step 2: Determine sign: isNeg = (dividend < 0) ^ (divisor < 0).
  3. Step 3: Convert to 64-bit absolute values: a = abs(dividend), b = abs(divisor).
  4. Step 4: Loop i from 31 down to 0: if a >= (b << i), a -= (b << i), quotient |= (1LL << i).
  5. Step 5: Apply sign and clamp to [INT_MIN, INT_MAX].

Binary Long Division Trace: 10 / 3

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Check i = 1
Visual state
Values and pointers at this exact step
pointers
S
4
2
0
1
↑ i = 1
Check / comparison
10 >= 6 -> subtract 6
Decision / next transition
quotient = 2, dividend = 4.
Why this step matters

Step 1: Check i = 1. (3 << 1) = 6. 10 >= 6 is true. dividend becomes 10 - 6 = 4. quotient += (1 << 1) = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <cmath>
4
5using namespace std;
6
7class Solution {
8public:
9 int divide(int dividend, int divisor) {
10 if (dividend == INT_MIN && divisor == -1) return INT_MAX;
11 bool isNeg = (dividend < 0) ^ (divisor < 0);
12 long long a = abs((long long)dividend);
13 long long b = abs((long long)divisor);
14 long long quotient = 0;
15
16 for (int i = 31; i >= 0; --i) {
17 if ((a >> i) >= b) {
18 quotient += (1LL << i);
19 a -= (b << i);
20 }
21 }
22
23 long long res = isNeg ? -quotient : quotient;
24 if (res > INT_MAX) return INT_MAX;
25 if (res < INT_MIN) return INT_MIN;
26 return (int)res;
27 }
28};
29
30int main() {
31 Solution sol;
32 cout << "Optimal (10, 3): " << sol.divide(10, 3) << endl; // 3
33 cout << "Optimal (7, -3): " << sol.divide(7, -3) << endl; // -2
34 cout << "Optimal (-2147483648, -1): " << sol.divide(-2147483648, -1) << endl; // 2147483647
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(1) (32 iterations)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Repeated SubtractionO(dividend / divisor)O(1)Repeatedly subtract divisor from dividend until dividend < divisor, counting subtractions.Linear subtraction step by step.
2.Better — Exponential Doubling in LoopO((log(dividend/divisor))^2)O(1)While dividend >= divisor, double divisor (divisor << 1) and count (count << 1) until it exceeds dividend, then subtract.Multiple exponential searches.
3.Optimal — Direct 31-to-0 Bit Long DivisionOptimalO(1) (at most 32 steps)O(1)Iterate shift i from 31 down to 0. If dividend >= (divisor << i), subtract and add (1 << i) to quotient.32 shift-comparisons.

Common Pitfalls & Crucial Edge Cases

Taking `abs(INT_MIN)` directly

abs(-2147483648) overflows a 32-bit signed integer because INT_MAX is 2147483647. Use long long or work entirely in negative numbers.

Linear subtraction timeout

while (dividend >= divisor) { dividend -= divisor; count++; } triggers TLE when dividend = 231 - 1 and divisor = 1.

Incorrect sign determination

Using (dividend < 0) ^ (divisor < 0) is the cleanest way to determine whether the result is negative.

Crucial Edge Cases to Validate:

  • dividend = -2147483648, divisor = -1 — Overflows 32-bit signed integer; must return 2147483647 (INT_MAX).
  • divisor = 1 or -1 — Result is dividend or -dividend, guarding against INT_MIN overflow.
  • dividend == divisor — Quotient is 1, remainder is 0.
  • abs(dividend) < abs(divisor) — Quotient is immediately 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify integer overflow rules immediately: ask how 32-bit overflow should be handled.
  2. Explain the analogy to long division in base 2: we find the largest power of 2 such that divisor * 2^k <= dividend.
  3. Show how you handle negative numbers safely without triggering signed integer overflow.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does bitwise exponential search achieve division without using multiplication or division operators?

2.Why is dividend = INT_MIN (-231) and divisor = -1 a critical edge case?

3.What is the time complexity of the bit-shifting division algorithm?

Back to DSA Sheet