Implement integer division without using division
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two 32-bit signed integers `dividend` and `divisor`.
Implement a function that divides `dividend` by `divisor` and returns the **integer quotient**, **without** using the multiplication `*`, division `/`, or modulo `%` operators.
The result should be truncated toward zero (i.e., rounded toward 0, not toward −∞ or +∞).
Assume:
- `divisor` is not zero.
- The range of 32-bit signed integers is from −2³¹ to 2³¹ − 1.
You must:
- Handle potential overflow correctly. If the result overflows the 32-bit signed integer range, return `2^31 - 1` (the maximum 32-bit signed integer).
- Aim for a time complexity **better than O(|dividend|)** (i.e., you should not subtract `divisor` from `dividend` one unit at a time).
**Function signature example (language-agnostic):**
```text
int divide(int dividend, int divisor);
```
Explain the algorithm you would use and then implement the function in the programming language of your choice.
Quick Answer: This question evaluates proficiency in implementing low-level integer arithmetic and algorithmic optimization, including correct handling of overflow and edge cases within 32-bit signed integer constraints.
Given two 32-bit signed integers dividend and divisor, implement integer division and return the integer quotient. You may not use the multiplication (*), division (/), or modulo (%) operators. The quotient must be truncated toward zero. If the result would overflow the 32-bit signed integer range, return 2^31 - 1.
Constraints
- -2^31 <= dividend <= 2^31 - 1
- -2^31 <= divisor <= 2^31 - 1
- divisor != 0
- Do not use multiplication (*), division (/), or modulo (%) operators
- The algorithm should be better than O(|dividend|)
Examples
Input: (10, 3)
Expected Output: 3
Explanation: 10 divided by 3 is 3.333..., which truncates toward zero to 3.
Input: (7, -3)
Expected Output: -2
Explanation: 7 divided by -3 is -2.333..., which truncates toward zero to -2.
Hints
- Instead of subtracting the divisor one time at a time, try subtracting the largest doubled version of the divisor that fits into the remaining dividend.
- Bit shifts can be used to efficiently double numbers and build the quotient from powers of two.