Problem Description

This problem asks you to implement integer division between two numbers (dividend and divisor) without using the multiplication (*), division (/), or modulo (%) operators.

The division should follow truncation rules toward zero, meaning:

• Positive results lose their decimal part (e.g., 8.345 becomes 8)
• Negative results also truncate toward zero (e.g., -2.7335 becomes -2)

The function should return the quotient (the integer result of the division).

Key Constraints:

• The environment only supports 32-bit signed integers with range [-2^31, 2^31 - 1]
• If the actual quotient exceeds 2^31 - 1, return 2^31 - 1 (overflow case)
• If the actual quotient is less than -2^31, return -2^31 (underflow case)

Solution Strategy: The solution uses repeated subtraction with bit manipulation optimization. Since division is essentially counting how many times the divisor can be subtracted from the dividend, the naive approach would subtract the divisor one at a time. However, this is inefficient for large numbers.

The optimization uses bit shifting (doubling) to speed up the process:

1. Convert both numbers to negative to avoid overflow issues (since -2^31 cannot be represented as a positive 32-bit integer)
2. For each iteration, find the largest multiple of the divisor (using left shifts to double it) that can be subtracted from the current dividend
3. Subtract this multiple and add the corresponding count to the answer
4. Repeat until the remaining dividend is smaller than the divisor
5. Apply the correct sign to the final result

The bit shifting approach reduces time complexity from O(dividend/divisor) to O(log(dividend/divisor)).

Intuition

Think about how we learned division in elementary school - it's essentially repeated subtraction. If we want to divide 20 by 3, we keep subtracting 3 from 20 until we can't subtract anymore: 20 - 3 - 3 - 3 - 3 - 3 - 3 = 2. We subtracted 6 times, so 20 ÷ 3 = 6.

The naive approach would be to implement this directly - keep subtracting the divisor from the dividend and count how many times we can do it. But imagine dividing 2^31 - 1 by 1 - we'd need to subtract over 2 billion times! This would definitely timeout.

The key insight is that we can subtract larger chunks at once. Instead of subtracting the divisor one at a time, what if we could subtract divisor * 2, divisor * 4, divisor * 8, and so on? But wait - we can't use multiplication!

This is where bit shifting comes in. Left shifting a number by 1 position (x << 1) doubles it without using multiplication. So we can create multiples of the divisor using shifts: divisor << 1 is 2 * divisor, divisor << 2 is 4 * divisor, etc.

The strategy becomes: find the largest multiple of the divisor (created by shifting) that still fits into the dividend, subtract it, and repeat. It's like taking the biggest possible bite each time instead of nibbling.

For example, dividing 20 by 3:

• Can we subtract 3 << 2 = 12? Yes! Now we have 20 - 12 = 8, and we've effectively subtracted 4 times
• Can we subtract 3 << 1 = 6 from 8? Yes! Now we have 8 - 6 = 2, adding 2 more to our count
• Can we subtract 3 from 2? No, we're done. Total count: 4 + 2 = 6

One tricky detail: why convert everything to negative? In 32-bit signed integers, the range is [-2^31, 2^31 - 1]. Notice that -2^31 has no positive counterpart - converting it to positive would overflow! By working with negatives throughout, we avoid this edge case since all positive numbers can be safely converted to negative.

Learn more about Math patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Handle Special Cases:

if b == 1:
    return a
if a == -(2**31) and b == -1:
    return 2**31 - 1

• If divisor is 1, the quotient is simply the dividend
• The overflow case: -2^31 ÷ -1 = 2^31, which exceeds our limit, so we return 2^31 - 1

2. Determine the Sign:

sign = (a > 0 and b > 0) or (a < 0 and b < 0)

The result is positive if both numbers have the same sign, negative otherwise.

3. Convert to Negative Numbers:

a = -a if a > 0 else a
b = -b if b > 0 else b

As discussed, we work with negatives to avoid overflow. Both a (dividend) and b (divisor) are converted to negative values.

4. Main Division Loop:

ans = 0
while a <= b:  # Note: both are negative, so <= means |a| >= |b|

Continue as long as the absolute value of dividend is greater than or equal to the absolute value of divisor.

5. Find Largest Subtractable Multiple:

x = b
cnt = 1
while x >= (-(2**30)) and a <= (x << 1):
    x <<= 1
    cnt <<= 1

• Start with x = b (the divisor) and cnt = 1 (representing how many divisors this equals)
• Double x using left shift (x << 1) as long as:
  • x >= -(2^30): Prevents overflow when doubling (since -(2^30) << 1 = -(2^31))
  • a <= (x << 1): The doubled value still fits into the dividend
• Each time we double x, we also double cnt to track the multiple

6. Subtract and Accumulate:

a -= x
ans += cnt

Subtract the largest multiple found from the dividend and add the corresponding count to our answer.

7. Apply Sign and Return:

return ans if sign else -ans

Apply the sign determined in step 2 to get the final result.

Example Walkthrough: 20 ÷ 3

• After conversion to negatives: a = -20, b = -3
• First iteration:
  • Find largest multiple: -3 → -6 → -12 (stop at -12 since -24 would exceed -20)
  • Subtract: -20 - (-12) = -8, add cnt = 4 to answer
• Second iteration:
  • Find largest multiple: -3 → -6 (stop at -6 since -12 would exceed -8)
  • Subtract: -8 - (-6) = -2, add cnt = 2 to answer
• -2 > -3, so loop ends
• Result: 4 + 2 = 6

The time complexity is O(log n) where n is the quotient, since we're essentially doing binary search on the quotient value through bit shifting.

Example Walkthrough

Let's walk through dividing 15 ÷ 4 using the bit-shifting solution approach:

Initial Setup:

• Dividend = 15, Divisor = 4
• Sign will be positive (both numbers are positive)
• Convert to negatives: a = -15, b = -4
• Initialize ans = 0

Iteration 1:

• Start with a = -15, need to find largest multiple of -4 that fits
• Build multiples by doubling:
  • x = -4, cnt = 1
  • Can we double? Check if -15 <= (-4 << 1) = -8? Yes! So x = -8, cnt = 2
  • Can we double? Check if -15 <= (-8 << 1) = -16? No! Stop here
• Subtract the largest multiple: a = -15 - (-8) = -7
• Add to answer: ans = 0 + 2 = 2

Iteration 2:

• Start with a = -7, find largest multiple of -4 that fits
• Build multiples:
  • x = -4, cnt = 1
  • Can we double? Check if -7 <= (-4 << 1) = -8? No! Stop here
• Subtract: a = -7 - (-4) = -3
• Add to answer: ans = 2 + 1 = 3

Check Loop Condition:

• Is a = -3 still <= b = -4? No! (Remember, both are negative)
• Exit loop

Final Result:

• Apply sign (positive): ans = 3
• Return 3

Verification: 15 ÷ 4 = 3 with remainder 3, which truncates to 3 ✓

The key insight: instead of subtracting 4 three times (naive approach), we subtracted 8 once (which equals subtracting 4 twice) and then 4 once more - reducing our iterations from 3 to 2.

Solution Implementation

Time and Space Complexity

The time complexity of this division algorithm is O(log a × log b), where a is the dividend and b is the divisor.

The algorithm works by repeatedly subtracting multiples of the divisor from the dividend. The outer while loop runs at most O(log a) times because in each iteration, we subtract at least the divisor b from a, and in the worst case, we need a/b iterations which is bounded by O(log a) when we consider the doubling optimization.

The inner while loop performs bit shifting operations to find the largest multiple of b (in the form of b × 2^k) that can be subtracted from the current value of a. This loop runs at most O(log b) times in each iteration of the outer loop, as we double x each time until it exceeds a or reaches the boundary condition.

Since the inner loop runs O(log b) times for each of the O(log a) iterations of the outer loop, the total time complexity is O(log a × log b).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables like sign, ans, x, and cnt, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Working with Positive Numbers

The Pitfall: Many developers initially try to work with positive numbers by converting negative inputs to positive. This fails for the edge case where dividend = -2^31 because 2^31 cannot be represented in a 32-bit signed integer (maximum is 2^31 - 1).

# WRONG approach - causes overflow
dividend = abs(dividend)  # This fails when dividend = -2^31
divisor = abs(divisor)

The Solution: Always convert to negative numbers instead, since the negative range [-2^31, -1] is larger than the positive range [1, 2^31-1]:

# CORRECT approach
dividend = -dividend if dividend > 0 else dividend
divisor = -divisor if divisor > 0 else divisor

2. Overflow During Bit Shifting

The Pitfall: When doubling the divisor using left shift, forgetting to check for potential overflow can cause incorrect results or runtime errors:

# WRONG - no overflow check
while dividend <= (current_divisor << 1):
    current_divisor <<= 1
    current_quotient <<= 1

The Solution: Add a boundary check before shifting. Since we're working with negative numbers, check that the current value is >= -2^30 before doubling (because -2^30 << 1 = -2^31, which is the limit):

# CORRECT - includes overflow prevention
while current_divisor >= -(2**30) and dividend <= (current_divisor << 1):
    current_divisor <<= 1
    current_quotient <<= 1

3. Incorrect Sign Determination Logic

The Pitfall: Using XOR or other complex logic for sign determination can be error-prone:

# Confusing and error-prone
is_positive = (dividend < 0) ^ (divisor < 0) == 0

The Solution: Use clear, explicit logic that's easy to understand and verify:

# CORRECT and clear
is_positive = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)

4. Forgetting the Special Overflow Case

The Pitfall: Not handling the specific case of -2^31 ÷ -1, which mathematically equals 2^31 but exceeds the 32-bit signed integer range:

# WRONG - missing overflow handling
def divide(dividend, divisor):
    # ... rest of the code without checking for INT_MIN / -1

The Solution: Always check for this case explicitly at the beginning:

# CORRECT
if dividend == -(2**31) and divisor == -1:
    return 2**31 - 1

5. Incorrect Comparison Direction with Negative Numbers

The Pitfall: When working with negative numbers, the comparison operators can be counterintuitive:

# WRONG - using > instead of <= for negative numbers
while dividend > divisor:  # This is wrong when both are negative

The Solution: Remember that for negative numbers, a "smaller" value actually has a larger absolute value:

# CORRECT
while dividend <= divisor:  # -20 <= -3 means |20| >= |3|