Skip to main content

29 - Divide Two Integers

Difficulty: Medium | Pattern: Bit Manipulation | Company tags: Amazon, Google, Microsoft

Problem Statement​

Given two integers dividend and divisor, divide two integers without using multiplication, division, or 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 the environment cannot store 64-bit integers. If the quotient is outside the range [-2^31, 2^31 - 1], return 2^31 - 1.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -3

Approach: Bit Shifting — O(log² n)​

Key insight: Subtract the largest multiple of divisor (obtained by bit-shifting) from dividend. Accumulate quotient bits.

Algorithm Flow​

def divide(dividend: int, divisor: int) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -(2**31)
    
    # Overflow case
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX
    
    negative = (dividend < 0) != (divisor < 0)
    a, b = abs(dividend), abs(divisor)
    result = 0
    
    while a >= b:
        temp, multiple = b, 1
        while a >= (temp << 1):
            temp <<= 1
            multiple <<= 1
        a -= temp
        result += multiple
    
    return -result if negative else result

Dry Run​

dividend=10, divisor=3 → a=10, b=3

atempmultipleshift until a lt temp*2result
103→6→12(stop at 6)1→2a=10-6=42
43→6(stop at 3)1a=4-3=13
13 gt 1, exit

Result: 3 ✓

Edge Cases​

  • INT_MIN / -1 → overflow, return INT_MAX
  • dividend = 0 → return 0
  • divisor = 1 → return dividend
  • Signs differ → negative result

Complexity​

  • Time: O(log² n) — outer loop O(log n) iterations, inner loop O(log n) shifts each
  • Space: O(1)

Key Terms​

TermDefinition
Bit shiftingDoubling (<<) or halving a number by shifting its binary representation; used here to find the largest power-of-two multiple of the divisor.
Quotient accumulationBuilding the answer by summing powers of two (multiple) each time a shifted divisor is subtracted.
Overflow guardExplicit check for INT_MIN / -1, the one case whose true result exceeds the 32-bit signed range.
Sign normalizationWorking with absolute values and XOR-ing the sign bits, then reapplying sign at the end.

FAQ​

Q: Why not just use dividend // divisor in Python? A: The problem forbids multiplication, division, and mod to force you to demonstrate the bit-manipulation technique interviewers are testing for.

Q: Why does the inner while a >= (temp << 1) loop double temp instead of incrementing it? A: Doubling finds the largest multiple of the divisor that still fits under a in O(log n) steps instead of O(n), which is what gives the O(log² n) bound.

Q: What's the one case that overflows a 32-bit signed integer? A: INT_MIN / -1, since the mathematical result (2^31) is one more than INT_MAX; it must be special-cased and clamped to INT_MAX.

Q: How would you handle this in a language with true 64-bit or arbitrary-precision integers? A: The overflow-clamp check is unnecessary since the raw result would never exceed the type's range, but interviewers usually still ask you to include it to show awareness of the constraint.

Q: What's the common follow-up here? A: Prove the time complexity is O(log² n) (log n outer subtractions, each needing a log n shift search) and discuss whether it can be tightened to O(log n) with a precomputed table of shifted divisors.

Quick Revision​

  • Goal: divide two integers without *, /, or %, truncating toward zero.
  • Special-case INT_MIN / -1 up front — it's the only overflow scenario.
  • Normalize by working with abs(dividend) and abs(divisor), tracking sign separately.
  • Repeatedly find the largest divisor << k that still fits in the remaining a.
  • Subtract that shifted value, add the corresponding multiple (also a power of two) to the result.
  • Repeat until a < b (remaining dividend smaller than divisor).
  • Reapply the sign to the accumulated result before returning.
  • Time: O(log² n); Space: O(1).
  • The technique generalizes to any "repeated subtraction via doubling" problem.
  • Power/exponentiation problems using bit shifting, e.g. "Pow(x, n)" (fast exponentiation via binary shifts) — same doubling idea applied to multiplication instead of subtraction.
  • Bitwise arithmetic problems such as "Sum of Two Integers" (addition without +) — same theme of simulating arithmetic operators with bit operations.
  • "Add Binary" — grade-school binary addition, another arithmetic-simulation pattern.