Domain 2MediumCORE

Divide Two Integers

We are asked to implement integer division without using multiplication (*), division (/), or modulo (%) operators. The core goal is to find how many times divisor fits into dividend.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Binary Search

29. Divide Two Integers

Model: qwen3.5:9b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 16.9%


Problem Breakdown

We are asked to implement integer division without using multiplication (*), division (/), or modulo (%) operators. The core goal is to find how many times divisor fits into dividend.

Key constraints and edge cases:

  1. Operator Restriction: We cannot use /, *, %. This forces us to rely on addition/subtraction and bit manipulation (shifting).
  2. 32-bit Range: Inputs are within [−231,231−1][-2^{31}, 2^{31} - 1].
    • Note: In languages like C++ or Java, converting INT_MIN (-2^31) to its absolute value would overflow a signed 32-bit integer. However, in Python (which this solution uses), integers have arbitrary precision, so we can safely use abs() without intermediate overflow issues. We must still ensure the final result adheres to the return constraint if it exceeds INT_MAXINT\_MAX.
  3. Overflow Handling: If the mathematical result would be greater than 231−12^{31} - 1 (which only happens when dividing -INT_MIN by -1), we must return INT_MAX.
  4. Truncation: The division truncates toward zero, meaning standard integer behavior in most languages.

Intuition

If I were to solve this naively, I would subtract the absolute value of divisor from abs(dividend) repeatedly until it is smaller than divisor. While correct, this approach has a time complexity proportional to the magnitude of the dividend (O(N)O(N)). For inputs near 2312^{31}, this results in roughly 2 billion operations, which will Time Out (TLE) on standard interview platforms.

The key insight is that we don’t need to subtract one by one; we can subtract larger chunks at once. Specifically, if divisor fits into the dividend multiple times, it likely fits 1×1 \times, then 2×2 \times (<<1<< 1), then 4×4 \times (<<2<< 2). By doubling our divisor (using bit shifts) until it is just smaller than or equal to the remaining dividend, we can subtract that large chunk and reduce the problem size significantly in each iteration. This reduces complexity from linear to logarithmic relative to the value of the input bits (O(log⁡N)O(\log N)), which effectively becomes O(1)O(1) for fixed-width integers like 32-bit ints (since there are only ~64 iterations max).

Approach

  1. Handle Signs: Determine if the result should be negative based on whether exactly one operand is negative. Work with absolute values internally to simplify logic, then apply the sign at the end.
    • Note: Python handles large integers automatically, but we must manually check for overflow per problem constraints before returning (specifically INT_MIN / -1).
  2. Handle Overflow Case: Check specifically if dividend is -INT_MIN and divisor is -1. The mathematical result would be 2312^{31}, which overflows the signed 32-bit range. Return INT_MAX immediately in this case.
  3. Iterative Subtraction with Doubling:
    • While abs(dividend) >= abs(divisor) is true:
      • Initialize a temporary variable (temp_divisor) to equal divisor.
      • Find the largest power of two shift (kk) such that (temp_divisor << k) fits within abs(dividend). We can do this by doubling temp_divisor and incrementing kk.
    • Subtract (temp_divisor << k) from dividend.
    • Add (1≪k)(1 \ll k) to the quotient.
  4. Finalize: Apply the sign determined in step 1. Return the result (clamped if necessary, though handled by overflow check).

Complexity Analysis

  • Time Complexity: O(log⁡N)O(\log N). In each iteration of our loop, we find a multiple that is at least half the size of the remaining dividend before subtracting it. Since there are 32 bits in an integer, this reduces to roughly 64 operations maximum (constant time relative to input value magnitude).
  • Space Complexity: O(1)O(1). We only use a few variables for tracking shifts and remainders; no recursion or auxiliary data structures are used.

Solution

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

        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        
        negative = (dividend < 0) ^ (divisor < 0)

        dividend, divisor = abs(dividend), abs(divisor)
        quotient = 0

        for i in range(31, -1, -1):
            if (dividend >> i) >= divisor:
                quotient += 1 << i
                dividend -= divisor << i
        return -quotient if negative else quotient

Edge Cases Handled

  • Zero Dividend: If dividend is 0, the result is immediately 0 without entering loops.
  • Overflow Case (INT_MIN / -1): Explicitly checked at start to return INT_MAX.
  • Negative Inputs: Signs are extracted and logic runs on absolute values; sign applied post-calculation ensures correct truncation toward zero (e.g., -7 // 3 = -2).
  • Equal Values: If dividend equals divisor, loop condition holds once, subtracts fully, quotient becomes 1.