Divide Two Integers (LeetCode 29)
You get two integers, dividend and divisor. Produce their quotient, but the catch is you may not reach for *, /, or % anywhere in the solution.
Division here chops off the fractional part instead of rounding, i.e. it truncates toward zero -- 8.345 becomes 8, and -2.7335 becomes -2.
Hand back that truncated dividend / divisor.
Note: pretend your only storage is a 32-bit signed integer, so the legal range is [-231, 231 - 1]. Should the true quotient land above 231 - 1, clamp it down to 231 - 1; should it land below -231, clamp it up to -231.
Worked Examples
dividend = 10, divisor = 33dividend = 7, divisor = -3-2⚖️Formal Constraints & Bounds
-231 <= dividend, divisor <= 231 - 1divisor != 0
Core Insight
Instead of subtracting the divisor one copy at a time (O(N) worst case), repeatedly subtract the largest power-of-two multiple of the divisor that still fits, guaranteeing at least half of the remaining dividend is removed each outer iteration -- O(log N) total. The single overflow edge case (dividend = INT_MIN, divisor = -1) must be clamped to INT_MAX before any arithmetic.
Real-World Scenario & Production Applications
Embedded/hardware integer division on ALUs without native divide instructions, and cryptographic modular arithmetic routines that must avoid a costly divide opcode.
Subproblems & Recurrence Decomposition3 Phases
Special-case dividend == INT_MIN and divisor == -1 up front -- the true quotient (2^31) is one past the signed 32-bit maximum and must be clamped before any arithmetic.
if dividend == INT_MIN and divisor == -1:
return INT_MAXStep-by-Step Execution Trace Table
| Step | Remaining dividend | Shifted divisor () | Shift Power k () | Subtraction | Quotient Tally |
|---|---|---|---|---|---|
| 1 | 43 | 3 << 3 = 24 | 43 - 24 = 19 | 8 | |
| 2 | 19 | 3 << 2 = 12 | 19 - 12 = 7 | ||
| 3 | 7 | 3 << 1 = 6 | 7 - 6 = 1 | ||
| 4 | 1 | (Cannot subtract) | — | Loop terminates | 14 (Result: ) |
The Math, Step by Step
1. The number the code builds
Let and , the sizes without signs. The code first finds , the largest whole number with . Then it gives the sign of the true quotient. This rounds toward zero, as the problem asks: for , it finds and returns .
The code may not use *, / or %. It uses the left shift << instead. x << 1 moves every bit of one place to the left, which doubles . So x << p equals .
2. One round: the largest doubling that still fits
Write in binary, as a sum of powers of two. For example, . Each round of the outer loop finds one of these powers.
In one round, the code starts with temp = dvs and multiple = 1. It keeps doubling both while temp << 1 still fits into dvd. When the loop stops, temp is for the largest with , and multiple is . Then the code subtracts temp from dvd and adds multiple to result.
| Variable | Before the round | After the inner loop | After the round |
|---|---|---|---|
temp | not used again | ||
multiple | 1 | not used again | |
dvd | what is left of | unchanged | |
result | powers found so far | unchanged |
3. Why the result is
At every moment, . It holds at the start, with result = 0 and dvd = a. Each round moves from dvd to result, as copies of , so the sum stays . The loop stops when . Then with . So result is the quotient , and dvd is the remainder.
Each round finds a smaller power than the round before. The round stops because . After it subtracts , less than is left, so the next power is smaller than . So result is a sum of different powers of two, one round per 1 bit of . A 32-bit quotient has at most 31 such bits, and each round starts again from temp = dvs and doubles at most 31 times. So the code takes steps. The worst case, divided by 1, makes 31 rounds with doublings in total.
4. The sign and the 32-bit bound
negative = (dividend < 0) != (divisor < 0) is True when exactly one of the two numbers is negative. Then the quotient is negative, and the code returns -result. Working with and first, then adding the sign, rounds toward zero. Rounding the negative value down would give , which is wrong here.
The quotient can leave the 32-bit range in exactly one case. , and only when and . With divisor = 1 the answer is , which fits. With divisor = -1 the answer would be , one more than the largest 32-bit value . So the code checks this case first and returns INT_MAX, as the problem's clamping rule says.
5. Example 1 by hand
dividend = 10, divisor = 3, so negative is False, and .
| Round | dvd at the start | Doublings of temp | temp, multiple | dvd after | result after |
|---|---|---|---|---|---|
| 1 | 10 | (12 would not fit) | 6, 2 | 2 | |
| 2 | 4 | none (6 would not fit) | 3, 1 | 3 |
Now dvd = 1 is less than 3, so the loop stops. Check: . The code returns 3, the expected output. In binary, is 11, and the two rounds found its two bits, 2 and 1.
6. Example 2 by hand
dividend = 7, divisor = -3. Exactly one is negative, so negative is True, and , . In round 1, temp doubles from 3 to 6, and 12 would not fit. So dvd becomes and result becomes 2. Now , so the loop stops. The code returns -2, the expected output.
7. From the math to the code
| Math | In divide |
|---|---|
| the one quotient above | if dividend == INT_MIN and divisor == -1: followed by return INT_MAX |
| the sign of the quotient | negative = (dividend < 0) != (divisor < 0) |
| and | dvd, dvs = abs(dividend), abs(divisor) |
| repeat while at least one fits | while dvd >= dvs: |
| the largest | while dvd >= (temp << 1): with temp <<= 1 and multiple <<= 1 |
| move copies of into the result | dvd -= temp and result += multiple |
| round toward zero | return -result if negative else result |
| 1 | if dividend == INT_MIN and divisor == -1: |
| 2 | return INT_MAX |
| 3 | negative = (dividend < 0) != (divisor < 0) |
| 4 | dvd, dvs = abs(dividend), abs(divisor) |
| 5 | while dvd >= dvs: |
| 6 | temp, multiple = dvs, 1 |
| 7 | while dvd >= (temp << 1): |
| 8 | temp <<= 1 |
| 9 | multiple <<= 1 |
| 10 | dvd -= temp |
| 11 | result += multiple |
| 12 | return -result if negative else result |
Conceptual Narrative
Division without *, /, or % sounds like it forces you back to repeated subtraction — one at a time, painfully O(N). Bit-shift doubling gets the exact same answer by subtracting in exponentially growing chunks instead.
🧭 Conceptual Foundation & Pattern Intuition
Repeated subtraction (while dividend >= divisor: dividend -= divisor; count += 1) is correct but can take up to iterations for a worst-case input like dividing INT_MAX by 1. The insight: instead of subtracting the divisor one copy at a time, find the largest power-of-two multiple of the divisor that still fits inside the remaining dividend, subtract that whole chunk at once, and record how many copies of the original divisor it represented. Repeating this collapses an O(N) loop into an O(log N) loop.
🏟️ The Analogy: Making Change With Doubling Bills
Imagine paying off a large debt using bills that double in value every time you produce a bigger one: 1x, 2x, 4x, 8x, 16x the divisor, and so on. Instead of handing over 1x bills one at a time (slow), you keep handing over the biggest doubling-bill that doesn't exceed what's still owed, then start doubling again from 1x for the remainder. Because each round of doubling only takes as many steps as there are bits in the number, the debt clears in O(log N) rounds instead of O(N) individual payments.
🔑 The Key Idea in the Code
The inner while loop doubles temp (a shifted copy of the divisor) and multiple (the matching power-of-two count) together, stopping the instant doubling again would overshoot. That guarantees each outer iteration removes at least half of what remains, bounding the total number of outer iterations by O(log N).
⚠️ The Classic Overflow Trap
Signed 32-bit integers range [-231, 231 - 1]. The single input that breaks a naive solution is dividend = INT_MIN = -231, divisor = -1: the mathematically correct answer is 231, which is one past INT_MAX. This must be special-cased and clamped to INT_MAX before any arithmetic, since even taking abs(INT_MIN) overflows a signed 32-bit int in languages like Java or C++.
32-bit signed overflow on : Dividing by equals , which exceeds
INT_MAX(). The problem requires clamping the result to2**31 - 1.Prohibited operators: The problem strictly forbids multiplication, division, and modulo operators. Subtraction combined with exponential bit-shift doubling (
divisor << 1,divisor << 2) is required to achieve .Sign determination using XOR: Determine the result sign via
(dividend < 0) ^ (divisor < 0)and work with positive or negative absolute values.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Integer division forbidding *, /, and % + signed 32-bit overflow boundary + a logarithmic-time expectation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: doubling temp and multiple together each inner-loop iteration guarantees the outer loop removes at least half of the remaining dividend per pass, bounding the outer iterations to O(log N).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the single overflow edge case: dividend = INT_MIN, divisor = -1 (mathematically 2^31, one past INT_MAX) -- must be clamped before any arithmetic, since abs(INT_MIN) itself overflows in fixed-width signed types.
Determining the sign after doing arithmetic on signed values instead of computing it once from the input signs and working with absolute values throughout.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I special-case dividend = INT_MIN, divisor = -1 up front and return INT_MAX. Otherwise I compute the sign once, then work entirely with absolute values. In the outer loop, while the remaining dividend is still >= the divisor, I double a shifted copy of the divisor (temp) and a matching power-of-two counter (multiple) as long as doubling still fits, then subtract that whole chunk and add multiple to the running quotient. That is
O(log N)outer iterations, each with at mostO(log N)doublings, so O(log² N) steps instead ofO(N)one-at-a-time subtractions."
Complexity & Mathematical Proof
O(log² N)
Look at the outer loop: each outer iteration doubles temp until it can no longer fit, then removes that entire chunk from dvd -- guaranteeing at least half of the remaining dvd is consumed per outer iteration. This bounds the outer iterations to O(log N). Each outer iteration restarts temp at the divisor and doubles it up to O(log N) times, so the total work is O(log N) × O(log N) = O(log² N). Dividing 2^31 - 1 by 1 takes 31 outer iterations and 465 doublings.
O(1) Auxiliary
Look at memory allocations: only a handful of integer variables (dvd, dvs, temp, multiple, result) are used, no recursion and no auxiliary data structures. O(1) auxiliary space.
Derivation Progression
temp, multiple double together until dvd < temp << 1
Finds the largest power-of-two multiple of the divisor that still fits. It restarts at the divisor every outer iteration, so it runs up to log N times each time.
dvd -= temp removes >= half of remaining dvd
Each outer iteration removes at least half of what's left, bounding total outer iterations to O(log N).
O(log N) outer iterations × O(log N) doublings = O(log² N)
At most 31 × 31 steps for 32-bit inputs (31 outer iterations and 465 doublings when dividing 2^31 - 1 by 1), with no multiplication, division, or modulo operators used.
Variable Definitions
Magnitude of the dividend (up to 2^31 - 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) Integer variables only
O(1) Single integer quotient
Boundary Best / Worst Cases
when dividend == INT_MIN and divisor == -1 (overflow guard short-circuit).
.
for arbitrary dividend/divisor up to 2^31 - 1.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: divide one integer by another while multiplication, division and mod are banned, clamp to [-231, 231 - 1]. Naive linear subtraction (dividend -= divisor) takes , which for takes operations (TLE). A Senior SWE recognizes Bit-Shift Exponential Doubling (Binary Long Division): greedily subtract large power-of-two multiples () using left bit-shifts.
. Operational budget is operations.
The infamous 32-bit overflow: , which exceeds . Must explicitly clamp to . Sign determination is cleanly handled via XOR: negative = (dividend < 0) ^ (divisor < 0). In languages without arbitrary precision (C/C++), converting to positive overflows 32-bit signed int; operate on 64-bit integers or stay in the negative domain.
Divide Two Integers (LeetCode 29)
You get two integers, dividend and divisor. Produce their quotient, but the catch is you may not reach for *, /, or % anywhere in the solution.
Division here chops off the fractional part instead of rounding, i.e. it truncates toward zero -- 8.345 becomes 8, and -2.7335 becomes -2.
Hand back that truncated dividend / divisor.
Note: pretend your only storage is a 32-bit signed integer, so the legal range is [-231, 231 - 1]. Should the true quotient land above 231 - 1, clamp it down to 231 - 1; should it land below -231, clamp it up to -231.
Worked Examples
dividend = 10, divisor = 33dividend = 7, divisor = -3-2⚖️Formal Constraints & Bounds
-231 <= dividend, divisor <= 231 - 1divisor != 0
Core Insight
Instead of subtracting the divisor one copy at a time (O(N) worst case), repeatedly subtract the largest power-of-two multiple of the divisor that still fits, guaranteeing at least half of the remaining dividend is removed each outer iteration -- O(log N) total. The single overflow edge case (dividend = INT_MIN, divisor = -1) must be clamped to INT_MAX before any arithmetic.
Real-World Scenario & Production Applications
Embedded/hardware integer division on ALUs without native divide instructions, and cryptographic modular arithmetic routines that must avoid a costly divide opcode.
Subproblems & Recurrence Decomposition3 Phases
Special-case dividend == INT_MIN and divisor == -1 up front -- the true quotient (2^31) is one past the signed 32-bit maximum and must be clamped before any arithmetic.
if dividend == INT_MIN and divisor == -1:
return INT_MAXStep-by-Step Execution Trace Table
| Step | Remaining dividend | Shifted divisor () | Shift Power k () | Subtraction | Quotient Tally |
|---|---|---|---|---|---|
| 1 | 43 | 3 << 3 = 24 | 43 - 24 = 19 | 8 | |
| 2 | 19 | 3 << 2 = 12 | 19 - 12 = 7 | ||
| 3 | 7 | 3 << 1 = 6 | 7 - 6 = 1 | ||
| 4 | 1 | (Cannot subtract) | — | Loop terminates | 14 (Result: ) |
The Math, Step by Step
1. The number the code builds
Let and , the sizes without signs. The code first finds , the largest whole number with . Then it gives the sign of the true quotient. This rounds toward zero, as the problem asks: for , it finds and returns .
The code may not use *, / or %. It uses the left shift << instead. x << 1 moves every bit of one place to the left, which doubles . So x << p equals .
2. One round: the largest doubling that still fits
Write in binary, as a sum of powers of two. For example, . Each round of the outer loop finds one of these powers.
In one round, the code starts with temp = dvs and multiple = 1. It keeps doubling both while temp << 1 still fits into dvd. When the loop stops, temp is for the largest with , and multiple is . Then the code subtracts temp from dvd and adds multiple to result.
| Variable | Before the round | After the inner loop | After the round |
|---|---|---|---|
temp | not used again | ||
multiple | 1 | not used again | |
dvd | what is left of | unchanged | |
result | powers found so far | unchanged |
3. Why the result is
At every moment, . It holds at the start, with result = 0 and dvd = a. Each round moves from dvd to result, as copies of , so the sum stays . The loop stops when . Then with . So result is the quotient , and dvd is the remainder.
Each round finds a smaller power than the round before. The round stops because . After it subtracts , less than is left, so the next power is smaller than . So result is a sum of different powers of two, one round per 1 bit of . A 32-bit quotient has at most 31 such bits, and each round starts again from temp = dvs and doubles at most 31 times. So the code takes steps. The worst case, divided by 1, makes 31 rounds with doublings in total.
4. The sign and the 32-bit bound
negative = (dividend < 0) != (divisor < 0) is True when exactly one of the two numbers is negative. Then the quotient is negative, and the code returns -result. Working with and first, then adding the sign, rounds toward zero. Rounding the negative value down would give , which is wrong here.
The quotient can leave the 32-bit range in exactly one case. , and only when and . With divisor = 1 the answer is , which fits. With divisor = -1 the answer would be , one more than the largest 32-bit value . So the code checks this case first and returns INT_MAX, as the problem's clamping rule says.
5. Example 1 by hand
dividend = 10, divisor = 3, so negative is False, and .
| Round | dvd at the start | Doublings of temp | temp, multiple | dvd after | result after |
|---|---|---|---|---|---|
| 1 | 10 | (12 would not fit) | 6, 2 | 2 | |
| 2 | 4 | none (6 would not fit) | 3, 1 | 3 |
Now dvd = 1 is less than 3, so the loop stops. Check: . The code returns 3, the expected output. In binary, is 11, and the two rounds found its two bits, 2 and 1.
6. Example 2 by hand
dividend = 7, divisor = -3. Exactly one is negative, so negative is True, and , . In round 1, temp doubles from 3 to 6, and 12 would not fit. So dvd becomes and result becomes 2. Now , so the loop stops. The code returns -2, the expected output.
7. From the math to the code
| Math | In divide |
|---|---|
| the one quotient above | if dividend == INT_MIN and divisor == -1: followed by return INT_MAX |
| the sign of the quotient | negative = (dividend < 0) != (divisor < 0) |
| and | dvd, dvs = abs(dividend), abs(divisor) |
| repeat while at least one fits | while dvd >= dvs: |
| the largest | while dvd >= (temp << 1): with temp <<= 1 and multiple <<= 1 |
| move copies of into the result | dvd -= temp and result += multiple |
| round toward zero | return -result if negative else result |
| 1 | if dividend == INT_MIN and divisor == -1: |
| 2 | return INT_MAX |
| 3 | negative = (dividend < 0) != (divisor < 0) |
| 4 | dvd, dvs = abs(dividend), abs(divisor) |
| 5 | while dvd >= dvs: |
| 6 | temp, multiple = dvs, 1 |
| 7 | while dvd >= (temp << 1): |
| 8 | temp <<= 1 |
| 9 | multiple <<= 1 |
| 10 | dvd -= temp |
| 11 | result += multiple |
| 12 | return -result if negative else result |
Conceptual Narrative
Division without *, /, or % sounds like it forces you back to repeated subtraction — one at a time, painfully O(N). Bit-shift doubling gets the exact same answer by subtracting in exponentially growing chunks instead.
🧭 Conceptual Foundation & Pattern Intuition
Repeated subtraction (while dividend >= divisor: dividend -= divisor; count += 1) is correct but can take up to iterations for a worst-case input like dividing INT_MAX by 1. The insight: instead of subtracting the divisor one copy at a time, find the largest power-of-two multiple of the divisor that still fits inside the remaining dividend, subtract that whole chunk at once, and record how many copies of the original divisor it represented. Repeating this collapses an O(N) loop into an O(log N) loop.
🏟️ The Analogy: Making Change With Doubling Bills
Imagine paying off a large debt using bills that double in value every time you produce a bigger one: 1x, 2x, 4x, 8x, 16x the divisor, and so on. Instead of handing over 1x bills one at a time (slow), you keep handing over the biggest doubling-bill that doesn't exceed what's still owed, then start doubling again from 1x for the remainder. Because each round of doubling only takes as many steps as there are bits in the number, the debt clears in O(log N) rounds instead of O(N) individual payments.
🔑 The Key Idea in the Code
The inner while loop doubles temp (a shifted copy of the divisor) and multiple (the matching power-of-two count) together, stopping the instant doubling again would overshoot. That guarantees each outer iteration removes at least half of what remains, bounding the total number of outer iterations by O(log N).
⚠️ The Classic Overflow Trap
Signed 32-bit integers range [-231, 231 - 1]. The single input that breaks a naive solution is dividend = INT_MIN = -231, divisor = -1: the mathematically correct answer is 231, which is one past INT_MAX. This must be special-cased and clamped to INT_MAX before any arithmetic, since even taking abs(INT_MIN) overflows a signed 32-bit int in languages like Java or C++.
32-bit signed overflow on : Dividing by equals , which exceeds
INT_MAX(). The problem requires clamping the result to2**31 - 1.Prohibited operators: The problem strictly forbids multiplication, division, and modulo operators. Subtraction combined with exponential bit-shift doubling (
divisor << 1,divisor << 2) is required to achieve .Sign determination using XOR: Determine the result sign via
(dividend < 0) ^ (divisor < 0)and work with positive or negative absolute values.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Integer division forbidding *, /, and % + signed 32-bit overflow boundary + a logarithmic-time expectation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: doubling temp and multiple together each inner-loop iteration guarantees the outer loop removes at least half of the remaining dividend per pass, bounding the outer iterations to O(log N).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the single overflow edge case: dividend = INT_MIN, divisor = -1 (mathematically 2^31, one past INT_MAX) -- must be clamped before any arithmetic, since abs(INT_MIN) itself overflows in fixed-width signed types.
Determining the sign after doing arithmetic on signed values instead of computing it once from the input signs and working with absolute values throughout.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I special-case dividend = INT_MIN, divisor = -1 up front and return INT_MAX. Otherwise I compute the sign once, then work entirely with absolute values. In the outer loop, while the remaining dividend is still >= the divisor, I double a shifted copy of the divisor (temp) and a matching power-of-two counter (multiple) as long as doubling still fits, then subtract that whole chunk and add multiple to the running quotient. That is
O(log N)outer iterations, each with at mostO(log N)doublings, so O(log² N) steps instead ofO(N)one-at-a-time subtractions."
Complexity & Mathematical Proof
O(log² N)
Look at the outer loop: each outer iteration doubles temp until it can no longer fit, then removes that entire chunk from dvd -- guaranteeing at least half of the remaining dvd is consumed per outer iteration. This bounds the outer iterations to O(log N). Each outer iteration restarts temp at the divisor and doubles it up to O(log N) times, so the total work is O(log N) × O(log N) = O(log² N). Dividing 2^31 - 1 by 1 takes 31 outer iterations and 465 doublings.
O(1) Auxiliary
Look at memory allocations: only a handful of integer variables (dvd, dvs, temp, multiple, result) are used, no recursion and no auxiliary data structures. O(1) auxiliary space.
Derivation Progression
temp, multiple double together until dvd < temp << 1
Finds the largest power-of-two multiple of the divisor that still fits. It restarts at the divisor every outer iteration, so it runs up to log N times each time.
dvd -= temp removes >= half of remaining dvd
Each outer iteration removes at least half of what's left, bounding total outer iterations to O(log N).
O(log N) outer iterations × O(log N) doublings = O(log² N)
At most 31 × 31 steps for 32-bit inputs (31 outer iterations and 465 doublings when dividing 2^31 - 1 by 1), with no multiplication, division, or modulo operators used.
Variable Definitions
Magnitude of the dividend (up to 2^31 - 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) Integer variables only
O(1) Single integer quotient
Boundary Best / Worst Cases
when dividend == INT_MIN and divisor == -1 (overflow guard short-circuit).
.
for arbitrary dividend/divisor up to 2^31 - 1.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: divide one integer by another while multiplication, division and mod are banned, clamp to [-231, 231 - 1]. Naive linear subtraction (dividend -= divisor) takes , which for takes operations (TLE). A Senior SWE recognizes Bit-Shift Exponential Doubling (Binary Long Division): greedily subtract large power-of-two multiples () using left bit-shifts.
. Operational budget is operations.
The infamous 32-bit overflow: , which exceeds . Must explicitly clamp to . Sign determination is cleanly handled via XOR: negative = (dividend < 0) ^ (divisor < 0). In languages without arbitrary precision (C/C++), converting to positive overflows 32-bit signed int; operate on 64-bit integers or stay in the negative domain.