Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Two integers are given: dividend and divisor.

The task is to return the integer quotient of dividend / divisor, but with three constraints that make the problem interesting:

  • multiplication, division, and modulus operators are off limits
  • the answer must truncate toward zero
  • the result must fit inside the signed 32-bit integer range

That last rule creates one annoying edge case: dividing -2^31 by -1 should mathematically produce 2^31, but that is one past the allowed maximum, so the correct answer is 2^31 - 1.

Why the obvious idea is too slow

The most direct idea is repeated subtraction:

  • subtract divisor from dividend
  • count how many times that works

That is logically correct, but it is far too slow when the quotient is large. For example, 1_000_000_000 / 1 would need a billion subtractions.

So the real goal is not just to subtract. It is to subtract large chunks at a time.

The key insight

Division is repeated subtraction, and repeated subtraction becomes fast if the subtracted values grow exponentially.

Instead of subtracting:

  • divisor
  • divisor
  • divisor

the algorithm should try subtracting:

  • divisor
  • 2 * divisor
  • 4 * divisor
  • 8 * divisor

Those are just left shifts in binary. This turns the problem into a form of binary long division: build the quotient from the largest power of two downward.

For example, with 43 / 5:

  • 5 << 3 = 40 fits, so the quotient includes 8 and the remainder becomes 3
  • 5 << 2 = 20 does not fit
  • 5 << 1 = 10 does not fit
  • 5 << 0 = 5 does not fit

So the final quotient is 8.

This works because every integer quotient can be written as a sum of powers of two. The algorithm is simply deciding which quotient bits should be turned on.

How to derive the optimal solution in an interview

A clean interview progression looks like this:

  1. Start with repeated subtraction, because it directly matches the definition of division.
  2. Point out the performance problem when the quotient is huge.
  3. Notice that if one copy of the divisor fits, maybe two fit, then four, then eight.
  4. Reframe that doubling process as checking binary place values from high to low.
  5. Track the sign separately, compute the magnitude of the quotient, then re-apply the sign at the end.
  6. Clamp the one overflow case required by the 32-bit constraint.

There are two closely related implementations:

  • repeated doubling inside a loop
  • a cleaner bit-by-bit scan from the largest possible shift down to zero

Both are based on the same idea. The second version is usually easier to reason about and easier to present as the final answer.

Python solution

The implementation below uses binary long division.

It first handles the special overflow case and the sign. Then it works with non-negative magnitudes, scanning from the largest useful left shift down to zero. Whenever a shifted divisor still fits inside the remaining dividend, that chunk is subtracted and the matching power of two is added to the quotient.

This gives:

  • Time: O(log(|dividend|))
  • Extra space: O(1)

For LeetCode’s fixed 32-bit constraints, the number of iterations is effectively capped by the bit width.

INT_MIN = -(1 << 31)
INT_MAX = (1 << 31) - 1


def clamp_to_int32(value: int) -> int:
    """Clamp a value to the signed 32-bit integer range."""
    if value < INT_MIN:
        return INT_MIN
    if value > INT_MAX:
        return INT_MAX
    return value


def to_non_negative(value: int) -> int:
    """Return the magnitude of an integer without using abs()."""
    return -value if value < 0 else value


def divide_without_operators(dividend: int, divisor: int) -> int:
    """
    Divide two integers without using multiplication, division, or modulus.

    The quotient is truncated toward zero and clamped to the signed 32-bit
    integer range.
    """
    if divisor == 0:
        raise ZeroDivisionError("division by zero")

    # This is the only input pair whose exact mathematical answer overflows
    # a signed 32-bit integer.
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    negative_result = (dividend < 0) != (divisor < 0)
    remaining_dividend = to_non_negative(dividend)
    positive_divisor = to_non_negative(divisor)

    if remaining_dividend < positive_divisor:
        return 0

    quotient = 0
    highest_shift = (
        remaining_dividend.bit_length() - positive_divisor.bit_length()
    )

    # Build the quotient one binary digit at a time, from largest to smallest.
    for shift in range(highest_shift, -1, -1):
        shifted_divisor = positive_divisor << shift
        if shifted_divisor > remaining_dividend:
            continue

        remaining_dividend -= shifted_divisor
        quotient += 1 << shift

    signed_quotient = -quotient if negative_result else quotient
    return clamp_to_int32(signed_quotient)


class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        """LeetCode entry point."""
        return divide_without_operators(dividend=dividend, divisor=divisor)

Interview follow-ups

What if the interviewer asks for the version based on repeated doubling instead of a fixed bit scan?

That solution is the same idea in a slightly different shape. For each outer-loop step, it keeps doubling the divisor until the next doubling would be too large, then subtracts the largest valid chunk and adds the matching multiple to the quotient. It is often easier to discover on the fly because it grows naturally out of repeated subtraction. The bit-scan version is cleaner as a final answer because it makes the binary structure explicit and avoids re-finding the same shifts from scratch.

Why do many Java or C++ solutions convert everything to negative numbers first?

In fixed-width integer languages, abs(INT_MIN) overflows because the negative range is one larger than the positive range. Converting both numbers to negative values avoids that trap and keeps every intermediate value representable. Python does not have that overflow issue for plain integers, so the code above can work with non-negative magnitudes directly, but the negative-domain trick is still worth understanding because interviewers often ask about language portability.

Could this be solved with recursion?

Yes. A recursive version can repeatedly subtract the largest doubled divisor and then recurse on the remainder. The logic is correct and can be elegant, but it does not buy anything here. The iterative approach is simpler, uses constant auxiliary space, and avoids recursion overhead. In interviews, the iterative version is usually the better final answer unless the interviewer specifically wants a recursive derivation.

What changes if the problem asks for the remainder too?

Almost nothing. The algorithm already maintains the leftover value after subtracting all chosen shifted divisors. That leftover is the remainder magnitude. The only extra work is deciding what sign convention the problem wants for the remainder, because different languages and problem statements define signed remainder behavior differently. The quotient logic and time complexity stay the same.

Is the complexity really O(log n) instead of O(n)?

Yes, because the algorithm is no longer subtracting one divisor at a time. It is deciding quotient bits, and the number of quotient bits is logarithmic in the magnitude of the input. In the bit-scan version, each shift is examined once, so the work is proportional to the number of relevant bit positions. Under LeetCode’s 32-bit constraint, that is effectively constant time, but the more general way to describe it is O(log(|dividend|)) time with O(1) extra space.