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:
- Operator Restriction: We cannot use
/,*,%. This forces us to rely on addition/subtraction and bit manipulation (shifting). - 32-bit Range: Inputs are within .
- 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 useabs()without intermediate overflow issues. We must still ensure the final result adheres to the return constraint if it exceeds .
- Note: In languages like C++ or Java, converting
- Overflow Handling: If the mathematical result would be greater than (which only happens when dividing
-INT_MINby-1), we must returnINT_MAX. - 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 (). For inputs near , 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 , then (), then (). 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 (), which effectively becomes for fixed-width integers like 32-bit ints (since there are only ~64 iterations max).
Approach
- 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).
- Note: Python handles large integers automatically, but we must manually check for overflow per problem constraints before returning (specifically
- Handle Overflow Case: Check specifically if
dividendis-INT_MINanddivisoris-1. The mathematical result would be , which overflows the signed 32-bit range. ReturnINT_MAXimmediately in this case. - Iterative Subtraction with Doubling:
- While
abs(dividend) >= abs(divisor)is true:- Initialize a temporary variable (
temp_divisor) to equaldivisor. - Find the largest power of two shift () such that
(temp_divisor << k)fits withinabs(dividend). We can do this by doublingtemp_divisorand incrementing .
- Initialize a temporary variable (
- Subtract
(temp_divisor << k)fromdividend. - Add to the quotient.
- While
- Finalize: Apply the sign determined in step 1. Return the result (clamped if necessary, though handled by overflow check).
Complexity Analysis
- Time Complexity: . 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: . 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
dividendis 0, the result is immediately 0 without entering loops. - Overflow Case (
INT_MIN / -1): Explicitly checked at start to returnINT_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.