Divide Two Integers

Repeated subtraction computes division correctly, but it counts quotient units one at a time. Under interview constraints, that is the wrong scale of thinking. Build the quotient from binary-sized chunks: repeatedly select the largest doubled divisor that fits, subtract it, and record the matching power-of-two contribution.

Read the Contract Before the Code

We must compute a quotient without using multiplication, division, or remainder operators.

The contract creates four separate obligations:

• dividend and divisor are signed 32-bit integers.
• divisor is nonzero.
• The quotient truncates toward zero.
• The result must remain within:

[ [-2^{31}, 2^{31} - 1] ]

Truncation toward zero matters for negative inputs:

7 / -3  -> -2
-7 / 3  -> -2

This differs from floor division, which would return -3 for both cases.

The critical overflow boundary is:

-2^31 / -1 = 2^31

That mathematical result exceeds the maximum signed 32-bit integer, so the required return value is 2^31 - 1.

Keep the solution in five phases:

1. Determine the result sign.
2. Work with operand magnitudes.
3. Construct the quotient magnitude from doubled divisor chunks.
4. Restore the sign.
5. Clamp the result to the signed 32-bit range.

Arithmetic discovers the magnitude. Sign and range are output policy. Mixing those jobs is where many implementations become difficult to prove.

Recognize Binary Doubling

The brute-force baseline is straightforward:

remaining = dividend magnitude

while remaining >= divisor magnitude:
    remaining -= divisor magnitude
    quotient += 1

It is correct, but the loop can run once for every unit in the quotient. With a large dividend and a small divisor, that is wasted motion.

The useful recognition clues are:

• the inputs are integers;
• multiplication, division, and remainder are forbidden;
• the quotient represents repeated copies of one value.

Instead of subtracting one divisor at a time, batch copies into powers of two:

divisor
divisor << 1
divisor << 2
divisor << 3
...

A left shift by shift represents multiplying by (2^{shift}):

divisor << shift = divisor * 2^shift

The matching quotient contribution is:

1 << shift

For 43 / 5, the largest fitting chunk is:

5 << 3 = 40
1 << 3 = 8

Subtracting 40 contributes 8 to the quotient and leaves 3. Since 5 no longer fits, the quotient is 8.

The reusable pattern is:

When repeated unit work dominates a loop, batch it into powers-of-two chunks.

Separate Magnitude, Sign, and Range

The problem becomes easier to reason about when each obligation gets its own phase.

Magnitude

Find the quotient of the absolute values. The core loop works with:

dividend_magnitude
divisor_magnitude

The magnitude quotient is always nonnegative.

Sign

The result is negative exactly when the operands have opposite signs. Equal signs produce a nonnegative result. A zero dividend naturally produces zero regardless of the divisor's sign.

Truncation

After removing every divisor chunk that fits, the leftover magnitude is smaller than the divisor. Discarding that leftover produces truncation toward zero.

That is why Python's // operator cannot directly implement the contract:

-7 // 3 == -3

The required result is -2, not -3.

Range

Apply the 32-bit clamp after restoring the sign. The magnitude phase may produce 2^31 for -2^31 / -1; the output policy must reduce that value to 2^31 - 1.

The architecture is:

sign -> magnitudes -> quotient magnitude -> signed result -> clamp

This separation keeps sign handling and overflow handling out of the arithmetic loop.

Derive the Greedy State and Invariant

For the magnitude phase, track four values:

• remaining: the dividend magnitude not yet explained;
• chunk: the current doubled divisor magnitude;
• multiple: the quotient contribution represented by chunk;
• quotient_magnitude: the accumulated quotient magnitude.

Each outer iteration starts with one copy of the divisor:

chunk = divisor_magnitude
multiple = 1

Then double both values together while the next doubled chunk still fits:

while (chunk << 1) <= remaining:
    chunk <<= 1
    multiple <<= 1

When this inner loop stops, chunk is the largest power-of-two multiple of the divisor that fits the current remainder. Subtract it and record its matching quotient contribution:

remaining -= chunk
quotient_magnitude += multiple

The central invariant is:

original_dividend_magnitude = quotient_magnitude * divisor_magnitude + remaining, with remaining >= 0.

The implementation never needs to calculate that multiplication. It is the proof model for what the state means.

Why the greedy choice is exact

Let the divisor magnitude be (d), and suppose the current search selects:

[ \text{chunk} = d \cdot 2^k ]

The inner loop stopped because the next doubled chunk does not fit:

[ 2 \cdot \text{chunk} > \text{remaining}_{before} ]

Therefore:

[ \text{remaining}_{before} < 2 \cdot \text{chunk} ]

After subtracting the selected chunk:

[ \text{remaining}{after} = \text{remaining}{before} - \text{chunk} < \text{chunk} ]

That inequality is the important part. The next outer iteration resets chunk to the original divisor and searches again, but it cannot rediscover the same exponent: every fitting chunk must be at most the new remainder, and the new remainder is smaller than the chunk just removed.

So the control flow is:

1. Start a fresh search from one divisor.
2. Double until the largest fitting chunk is found.
3. Subtract that chunk.
4. Restart from the base divisor.
5. Rely on the smaller remainder to force a smaller next chunk.

The loop variable does not scan bit positions monotonically. The selected chunks are nevertheless strictly decreasing because the state becomes smaller after every subtraction.

For example, a quotient might be assembled as:

16 + 4 + 1

The multiple values represent those binary contributions. They are distinct because each later selected chunk is smaller than the previous one, not because the implementation maintains a permanently descending shift variable.

The invariant then finishes the proof. At termination, no full divisor fits:

[ 0 \leq \text{remaining} < d ]

And the invariant says:

[ A = Qd + \text{remaining} ]

where (A) is the original dividend magnitude and (Q) is the accumulated quotient magnitude. Since the remainder is nonnegative and smaller than (d), (Q) is exactly the integer quotient of (A) by (d).

For 43 / 5:

Step	remaining before	Selected chunk	multiple	remaining after
1	43	40	8	3

The next search starts from 5, but 5 > 3, so it selects nothing. The final remainder is below the divisor, and the magnitude quotient is 8.

Handle Signedness in Python and Fixed-Width Languages

The minimum signed 32-bit integer is:

-2^31

Its positive magnitude, 2^31, does not fit in a signed 32-bit integer. In a fixed-width language, blindly negating or taking the absolute value of MIN_INT can overflow.

Two common strategies are:

• use a wider integer type for intermediate magnitudes;
• keep values negative during the calculation because the negative range is one unit larger.

Python integers have arbitrary precision, so this implementation can safely represent:

abs(-(1 << 31)) == 1 << 31

That protects the intermediate magnitude calculation. It does not remove the output restriction. The explicit final clamp is still required.

A fixed-width implementation also needs a safe check before doubling. The expression representing chunk << 1 must not overflow before the program compares it with remaining. A wider intermediate type is usually the clearest choice.

Record the result sign before converting to magnitudes:

negative = (dividend < 0) != (divisor < 0)

The problem guarantees that divisor is nonzero, so division-by-zero handling is outside this contract.

Implement the Python Solution

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        MIN_INT = -(1 << 31)
        MAX_INT = (1 << 31) - 1

        negative = (dividend < 0) != (divisor < 0)

        dividend_magnitude = abs(dividend)
        divisor_magnitude = abs(divisor)

        quotient_magnitude = 0
        remaining = dividend_magnitude

        while remaining >= divisor_magnitude:
            chunk = divisor_magnitude
            multiple = 1

            while (chunk << 1) <= remaining:
                chunk <<= 1
                multiple <<= 1

            remaining -= chunk
            quotient_magnitude += multiple

        result = (
            -quotient_magnitude
            if negative
            else quotient_magnitude
        )

        if result > MAX_INT:
            return MAX_INT
        if result < MIN_INT:
            return MIN_INT

        return result

Each variable answers one obligation:

• negative captures the sign before magnitude conversion;
• remaining stores the unexplained dividend magnitude;
• chunk stores the current doubled divisor;
• multiple stores the matching quotient contribution;
• quotient_magnitude accumulates the answer without signedness complications.

The code uses shifts, comparisons, subtraction, addition, and abs. It does not use multiplication, division, modulo, floating point, or a hidden quotient operation.

Verify the Important Cases

Positive operands: 43 / 5

The largest fitting doubled divisor is 40, representing eight copies of 5:

remaining = 43
chunk = 40
multiple = 8

remaining = 43 - 40 = 3
quotient = 0 + 8 = 8

The next outer iteration begins from 5, but 5 > 3, so the loop terminates.

Opposite signs: -43 / 5

The magnitude calculation is unchanged:

magnitude quotient = 8

The operands have opposite signs, so the final result is:

-8

There is no separate floor-rounding step. Discarding the leftover magnitude during the magnitude phase already gives truncation toward zero.

The same reasoning gives:

43 / -5 -> -8

Dividend smaller than divisor: 3 / 5

The outer loop never runs:

quotient_magnitude = 0

Applying either sign still returns 0.

Zero dividend: 0 / -5

Again, the outer loop never runs. The result is 0.

Overflow: -2^31 / -1

The magnitude phase produces:

2^31

The operands have the same sign, so the mathematical result is positive. It exceeds MAX_INT, so the final clamp returns:

2^31 - 1

This is an output-policy boundary, not a failure of the binary-doubling method.

Prove Correctness and Analyze Cost

The invariant holds initially:

quotient_magnitude = 0
remaining = dividend_magnitude

so:

[ A = 0 \cdot d + A ]

Each selected chunk has the form:

[ \text{chunk} = m d ]

and satisfies:

[ 0 < \text{chunk} \leq \text{remaining} ]

After subtracting it and adding multiple = m to the quotient:

[ A = Qd + R ]

becomes:

[ A = (Q + m)d + (R - md) ]

Because the chunk fits, the new remainder remains nonnegative. The stopping condition additionally gives:

[ R_{\text{after}} < md ]

Therefore, every later selected chunk is strictly smaller than the current one, even though each outer iteration restarts its search from the base divisor.

When the outer loop finishes:

[ 0 \leq R < d ]

Thus:

[ A = Qd + R ]

with a valid remainder range. Q is the exact quotient of the magnitudes. Restoring the sign gives truncation toward zero, and the final clamp enforces the 32-bit output range.

For this repeated-doubling implementation:

• Time: (O(\log |dividend| \cdot \log |dividend|))
• Auxiliary space: (O(1))

There are logarithmically many selected chunks, and each fresh search performs logarithmically many doublings in the worst case.

Because the problem restricts inputs to 32-bit integers, the practical bound is small. A top-down scan over fixed bit positions can make that bound explicit as (O(32)), but the nested-doubling version exposes the greedy derivation directly. In an interview, I would choose the version whose state meaning, overflow behavior, and proof I can keep aligned under pressure.

Test the Failure Boundaries

Test representation and policy boundaries, not only ordinary positive division.

Case	Expected result	What it checks
0 / 5	0	Zero dividend
0 / -5	0	Zero with negative divisor
3 / 5	0	Dividend smaller than divisor
7 / 3	2	Positive truncation
7 / -3	-2	Opposite signs
-7 / 3	-2	Truncation toward zero
-7 / -3	2	Equal negative signs
(2^31 - 1) / 1	2^31 - 1	Maximum dividend
-2^31 / 1	-2^31	Minimum dividend
-2^31 / -1	2^31 - 1	Positive overflow clamp
5 / 5	1	Exact quotient
5 / -5	-1	Exact negative quotient

For local validation, keep the submitted function operator-restricted but use an independent oracle in the test harness:

def oracle(dividend: int, divisor: int) -> int:
    quotient = abs(dividend) // abs(divisor)

    if (dividend < 0) != (divisor < 0):
        quotient = -quotient

    return max(-(1 << 31), min((1 << 31) - 1, quotient))

This oracle is not the submitted solution. Its job is to provide a different implementation of the semantics so you can compare many sign combinations and boundary values without copying the same greedy logic into the test.

A useful next step is to compare every small signed pair in a range such as -20 through 20, skipping a zero divisor:

for dividend in range(-20, 21):
    for divisor in range(-20, 21):
        if divisor != 0:
            assert (
                Solution().divide(dividend, divisor)
                == oracle(dividend, divisor)
            )

You can also inspect the final state directly while debugging:

0 <= remaining < divisor_magnitude

That assertion checks the exact termination condition promised by the proof. If it fails, the problem is in chunk selection or subtraction—not in sign restoration.

Common failures are predictable:

• using Python //, which floors instead of truncating toward zero;
• negating MIN_INT in a fixed-width signed type;
• allowing a left shift to overflow before checking whether the doubled chunk fits;
• returning the mathematical result without applying the 32-bit clamp;
• proving only that the loop terminates, without proving that the selected chunks form the quotient;
• describing a monotone bit scan while implementing repeated searches from the base divisor.

The transferable rule is simple: when a forbidden arithmetic operator hides repeated unit work, batch that work into powers-of-two chunks. Name the state invariant before coding. Keep magnitude arithmetic separate from sign and range policy. Then attack zero, opposite signs, the minimum integer, and the clamp boundary deliberately.

A bit shift is only the visible tool. The durable skill is recognizing when greedy binary-sized batching turns an impractical count into a small, provable sequence of state transitions.