Leetcode 29: Divide Two Integers

1. Problem Statement (Simple Explanation):

You are given two integers:

dividend
divisor (non-zero)

You must compute:

Subject to:

You cannot use:

multiplication (*)
division (/)
modulo (%)

You must handle 32-bit signed integer range:

[-231,231-1]=[-2147483648,2147483647]

If the quotient is strictly greater than 231 - 1, return 231 - 1.
If the quotient is strictly less than -231, return -231.

Truncation toward zero means:

8 / 3 = 2.66... → 2
-8 / 3 = -2.66... → -2

2. Examples:

Example 1:

Input: dividend = 10, divisor = 3

Exact division: 10 / 3 ≈ 3.3333 → truncated toward zero → 3.

Output: 3

Example 2:

Input: dividend = 7, divisor = -3

Exact division: 7 / -3 ≈ -2.3333 → truncated toward zero → -2.

Output: -2

Constraints:

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

3. Approach 1 – Naive Repeated Subtraction (Too Slow):

Conceptually:

Repeatedly subtract divisor from dividend and count how many times until remainder becomes smaller than divisor.

Problems:

If |dividend| and |divisor| are large (e.g., 109), this is O(|quotient|) → too slow.

We need something faster, ideally O(log(|dividend|).

4. Approach 2 – Bitwise Doubling (Fast, Like Binary Long Division):

We can simulate division using bit shifts and subtractions, similar to long division.

Ideas:

Work with absolute values to simplify, then apply the sign at the end.
Use bit shifting to subtract large multiples of divisor at once:

Instead of subtracting divisor one by one, find the largest multiple = divisor * 2k such that multiple <= dividend.
Subtract this multiple and add 2k to the quotient.

Repeat until the remaining dividend is smaller than divisor.

Since we can’t use *, we can generate divisor * 2k via divisor << k (left shift).

To avoid overflow issues, it's common to work in the negative domain (since range of negative integers is slightly larger: INT_MIN = -2147483648).

Handling Signs and Overflow:

Let:

INT_MAX = 2147483647
INT_MIN = -2147483648

Special overflow case:

dividend = INT_MIN, divisor = -1 → exact result is 2147483648, which is out of 32-bit signed range.
In this case, return INT_MAX.

Sign:

negative = (dividend < 0) XOR (divisor < 0)
Work with negative numbers to avoid overflow when negating INT_MIN.

We convert both to negative:

dvd = (dividend > 0) ? -dividend : dividend
dvs = (divisor > 0) ? -divisor : divisor

Then both dvd and dvs are ≤ 0.

Core Loop (Negative Domain):

We want to compute:

quotient=⌊dvd/dvs⌋

But both are negative, so dvd <= dvs <= 0 and the quotient will be positive or negative depending on signs.

Outline:

After finishing, if negative is true, result is -quotient, else quotient.

Pseudo-code (Bitwise Doubling, Negative Domain):

Complexity:

Let D = |dividend|:

Outer loop: each iteration subtracts at least half of current dvd (in magnitude).
Inner loop: finds largest power-of-two multiple via shifts (logarithmic).

Total time: O(logD)

Space: O(1)

5. Java code: