261. Divide Without Dividing
A vending machine's firmware has no multiplication or division hardware, only addition, subtraction, comparisons and bit shifts. It still has to answer "how many whole packs of size divisor fit into dividend units?" Given two 32-bit signed integers, return the quotient of dividend divided by divisor, truncated toward zero (so 7 / -2 is -3 and -7 / 2 is -3). You must not use the /, * or % operators or library division.
The divisor is never 0. Because the result must fit in a signed 32-bit integer, the single overflowing case, -2^31 / -1, must return 2^31 - 1. A loop that subtracts the divisor one copy at a time can take two billion steps, so aim for O(log |dividend|) time and O(1) extra space.
Example 1
- Input:
- dividend = 85, divisor = 6
- Output:
- 14
- Explanation:
85 divided by 6 truncates toward zero to 14.
Example 2
- Input:
- dividend = -1000, divisor = 33
- Output:
- -30
- Explanation:
-1000 divided by 33 truncates toward zero to -30.
Example 3
- Input:
- dividend = -2147483648, divisor = -1
- Output:
- 2147483647
- Explanation:
-2147483648 divided by -1 truncates toward zero to 2147483647.
Constraints
-231 ≤ dividend, divisor ≤ 231 - 1
divisor ≠ 0
The quotient is truncated toward zero; the only overflow case (-231 / -1) returns 231 - 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log |dividend|)
- Space
- O(1)