Divide Two Integers

Divide Two Integers is really about simulating long division with powers of two. Instead of subtracting the divisor one step at a time, keep doubling it with left shifts, subtract the biggest safe multiple, and add that multiple to the quotient. The main interview trap is overflow around INT_MIN, especially when dividend is -2147483648 and divisor is -1.

Problem Statement

You are given two 32-bit signed integers, dividend and divisor, and need to return the quotient after dividing them. The catch in Divide Two Integers is that you cannot use multiplication, division, or the modulo operator, so the result must come from arithmetic and bit reasoning rather than built-in division.

The quotient must truncate toward zero, so positive and negative fractions are both cut off instead of rounded. That means 10 divided by 3 becomes 3, while 7 divided by -3 becomes -2. Because inputs stay in signed integer range and divisor is never zero, the biggest edge case is the overflow result produced by INT_MIN divided by -1.

Examples

Example 1

Input: dividend = 10, divisor = 3

Output: 3

10/3 = 3.33333.. which is truncated to 3.

Example 2

Input: dividend = 7, divisor = -3

Output: -2

7/-3 = -2.33333.. which is truncated to -2.

Constraints

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

Solution Approach

Convert the sign decision into one boolean

First determine whether the final quotient should be negative by checking whether dividend and divisor have opposite signs. Then work with absolute values or, even safer, a negative-only representation so you can avoid the overflow that appears when trying to negate INT_MIN in 32-bit integer math.

Use bit shifts to find the largest subtractable multiple

The efficient pattern for Divide Two Integers is repeated doubling. Start from the divisor and keep left-shifting it until the next shift would exceed the remaining dividend. Subtract that largest shifted value, add the matching power of two to the answer, and repeat. This turns a slow repeated-subtraction idea into a logarithmic chunking process similar to binary long division.

Clamp the single overflow case and restore the sign

After building the magnitude of the quotient, apply the sign at the end. Before returning, handle the one forbidden 32-bit result: when dividend is -2147483648 and divisor is -1, the mathematical answer is 2147483648, which must be capped at 2147483647. Everything else fits once truncation toward zero is preserved during subtraction.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

A naive subtraction loop would take O(|quotient|) time and is too slow when the divisor is small. The bit manipulation approach repeatedly finds the largest shifted divisor that fits, so each outer iteration removes a large chunk and each inner doubling scan is logarithmic in the dividend range. In practice, the common implementation runs in O((log n)^2) time or O(log n) with precomputed shifts, and uses O(1) extra space.

What Interviewers Usually Probe

• They expect you to replace repeated subtraction with doubling or left shifts, not brute force loops.
• They are checking whether you know why INT_MIN cannot be safely negated in 32-bit signed arithmetic.
• They want truncation toward zero exactly, especially for mixed-sign inputs like 7 and -3.

Common Pitfalls or Variants

Common pitfalls

• Taking abs(INT_MIN) in a 32-bit type and silently overflowing before the real logic even starts.
• Using floor-style behavior for negatives and returning -3 for 7 divided by -3 instead of the required -2.
• Shifting the divisor too far without checking bounds, which can break comparisons or create incorrect subtraction steps.

Follow-up variants

• Return both quotient and remainder while still avoiding multiplication, division, and mod.
• Implement the same Divide Two Integers logic recursively by subtracting the largest doubled divisor each call.
• Generalize the bit-doubling idea to other repeated subtraction problems where powers of two compress the search.

FAQ

What is the core pattern in Divide Two Integers?

The core pattern is math plus bit manipulation. You simulate division by repeatedly subtracting the largest power-of-two multiple of the divisor that still fits inside the remaining dividend.

Why is repeated subtraction alone a bad solution for Divide Two Integers?

Plain repeated subtraction can take one step per unit of the quotient, which is far too slow when the divisor is 1 or -1. Bit shifts let you remove large multiples at once, which is the whole optimization.

Why is INT_MIN such a problem in this question?

In 32-bit signed integers, INT_MIN has no positive counterpart, so negating it overflows. That is why many correct solutions keep values negative during processing or use a wider type.

How do you handle negative results correctly?

Track whether dividend and divisor have opposite signs, compute the quotient magnitude with shifted subtraction, then apply the sign once at the end. This preserves truncation toward zero instead of accidentally flooring negative answers.

What time complexity should I state for the bit manipulation solution?

For the common shifting-and-subtracting implementation, O((log n)^2) is a safe answer because you may scan shifts for each large subtraction round. If you precompute shifted candidates once, you can describe it closer to O(log n) with O(1) extra space.