Problem statement

Divide two integers without using multiplication, division or the modulo operator, and return the quotient truncated toward zero.

If the result overflows a signed 32-bit integer, return 2147483647.

Example 1

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

Example 2

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

Example 3

Input: dividend = -2147483648, divisor = -1
Output: 2147483647
Explanation: The true answer overflows.

Constraints

• -2147483648 <= dividend, divisor <= 2147483647
• divisor != 0

Hints for Divide Two Integers

1. Hint 1

   Work with magnitudes and re-apply the sign at the end.

2. Hint 2

   Subtracting the divisor one at a time is far too slow — subtract divisor << shift instead, largest shift first.

3. Hint 3

   Only one input overflows: -2^31 / -1. Handle it up front, and use 64-bit intermediates so the shifts do not wrap.

How to solve Divide Two Integers

Subtract divisor << shift for shifts from 31 down to 0, accumulating 1 << shift into the quotient each time it fits; handle the single overflow case first.

Approach

1. Return 2³¹ - 1 for -2³¹ / -1.
2. Record the sign and take magnitudes.
3. For shift from 31 down: while (b << shift) <= a, subtract and add 1 << shift.
4. Apply the sign.

Why it works

This is binary long division: each shift tests one bit of the quotient, and taking the largest shifts first guarantees the remainder stays below the divisor.

Complexity

• Time — O(32)
• Space — O(1)

Pitfalls

• Use 64-bit intermediates for the shifted divisor.
• Subtracting one divisor at a time is O(quotient) and times out.

Reference solution

Python

def divide(dividend: int, divisor: int) -> int:
    if dividend == -2147483648 and divisor == -1:
        return 2147483647
    negative = (dividend < 0) != (divisor < 0)
    a, b = abs(dividend), abs(divisor)
    quotient = 0
    for shift in range(31, -1, -1):
        if (b << shift) <= a:
            a -= b << shift
            quotient += 1 << shift
    return -quotient if negative else quotient

Java

public static int divide(int dividend, int divisor) {
    if (dividend == -2147483648 && divisor == -1) return 2147483647;
    boolean negative = (dividend < 0) != (divisor < 0);
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    long quotient = 0;
    for (int shift = 31; shift >= 0; shift--) {
        if ((b << shift) <= a) {
            a -= b << shift;
            quotient += 1L << shift;
        }
    }
    return (int) (negative ? -quotient : quotient);
}

C++

int divide(int dividend, int divisor) {
    if (dividend == -2147483648 && divisor == -1) return 2147483647;
    bool negative = (dividend < 0) != (divisor < 0);
    long long a = dividend < 0 ? -(long long) dividend : (long long) dividend;
    long long b = divisor < 0 ? -(long long) divisor : (long long) divisor;
    long long quotient = 0;
    for (int shift = 31; shift >= 0; shift--) {
        if ((b << shift) <= a) {
            a -= b << shift;
            quotient += 1LL << shift;
        }
    }
    return (int) (negative ? -quotient : quotient);
}

JavaScript

var divide = function(dividend, divisor) {
    if (dividend === -2147483648 && divisor === -1) return 2147483647;
    const negative = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend);
    const b = Math.abs(divisor);
    let quotient = 0;
    for (let shift = 31; shift >= 0; shift--) {
        const scaled = b * Math.pow(2, shift);
        if (scaled <= a) {
            a -= scaled;
            quotient += Math.pow(2, shift);
        }
    }
    return negative ? -quotient : quotient;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium