29. Divide Two Integers - Detailed Explanation
Problem Statement
We are given two integers, dividend and divisor, and we need to compute the quotient after dividing the dividend by the divisor. The catch is that you cannot use multiplication, division, or the modulo operator. The result should be truncated toward zero. There is also a special requirement: if the result overflows a 32-bit signed integer (i.e., goes beyond [−2³¹, 2³¹ − 1]), then return 2³¹ − 1.
Examples
Example 1
- Input: dividend = 10, divisor = 3
- Output: 3
- Explanation: 10 / 3 is 3.3333…, which is truncated to 3.
Example 2
- Input: dividend = 7, divisor = -3
- Output: -2
- Explanation: 7 / (-3) is -2.3333…, which is truncated to -2.
Example 3
- Input: dividend = -2147483648, divisor = -1
- Output: 2147483647
- Explanation: The actual quotient is 2147483648, which overflows a 32-bit signed integer, so we return 2147483647.
Constraints
- The dividend and divisor are 32-bit signed integers.
- The divisor will never be 0.
Hints
-
Edge Cases & Signs: Think about how to handle negative numbers and what to do when the dividend is the smallest negative number.
-
Doubling Strategy: To reduce the number of operations, consider doubling the divisor (using bit shifting) until it becomes just less than or equal to the dividend, then subtract that value and repeat the process. This approach mimics binary search and significantly reduces time complexity.
Approach 1: Brute Force Subtraction
Explanation
The simplest idea is to repeatedly subtract the divisor from the dividend until what remains is smaller than the divisor. Each subtraction represents one unit added to the quotient.
- Step 1: Handle the sign by converting both numbers to positive and record if the result should be negative.
- Step 2: Use a loop to subtract the divisor from the dividend while keeping count of how many subtractions occur.
- Step 3: Make sure to handle the overflow case (e.g., when dividend = -2147483648 and divisor = -1).
Drawbacks
- This approach can be extremely slow when the dividend is large compared to the divisor because it performs many iterations (O(dividend/divisor) time complexity).
Visual Example
Consider dividend = 15 and divisor = 3:
- Subtraction steps: 15 - 3 = 12 (count = 1), 12 - 3 = 9 (count = 2), 9 - 3 = 6 (count = 3), 6 - 3 = 3 (count = 4), 3 - 3 = 0 (count = 5).
- The final quotient is 5.
Approach 2: Optimized Bit Manipulation (Doubling)
Explanation
Instead of subtracting the divisor one unit at a time, we can use bit manipulation to subtract larger chunks at once by doubling the divisor. The idea is similar to how we perform long division:
-
Step 1: Convert both numbers to positive values and determine the final sign based on their original signs.
-
Step 2: Initialize a quotient to 0.
-
Step 3: While the dividend is greater than or equal to the divisor, find the largest multiple of the divisor (using bit shifts) that is less than or equal to the dividend.
- For instance, keep doubling the divisor (i.e., divisor, divisor × 2, divisor × 4, …) until the doubled value would exceed the dividend.
- Subtract the largest found multiple from the dividend and add the corresponding multiple (a power of 2) to the quotient.
-
Step 4: Repeat until the dividend is smaller than the divisor.
-
Step 5: Apply the sign and check for overflow.
Visual Example
Consider dividend = 43 and divisor = 3:
- Iteration 1:
-
Start with multiple = 3, then double: 3, 6, 12, 24, 48. Since 48 > 43, the largest valid is 24.
-
Subtract 24 from 43 to get 19, and add 8 (since 3×8 = 24) to the quotient.
-
- Iteration 2:
- With remaining dividend = 19, double: 3, 6, 12, 24. Here 24 > 19, so take 12.
- Subtract 12 from 19 to get 7, and add 4 (since 3×4 = 12) to the quotient.
- Iteration 3:
- With remaining dividend = 7, double: 3, 6, 12. 12 > 7 so take 6.
- Subtract 6 from 7 to get 1, and add 2 to the quotient.
- Iteration 4:
- With remaining dividend = 1, 3 > 1 so we stop.
- Final Quotient: 8 + 4 + 2 = 14.
Code in Python
Below is the Python implementation using the optimized doubling approach.
Code in Java
Complexity Analysis
- Time Complexity:
- Brute Force: O(|dividend/divisor|) in the worst case.
- Optimized Approach: O(log(dividend)) because we double the divisor each time.
- Space Complexity: O(1) for both approaches.
Step-by-Step Walkthrough
Let’s walk through the optimized approach with dividend = 43 and divisor = 3:
- Convert both numbers to positive: dividend = 43, divisor = 3.
- Iteration 1:
- Start with temp = 3 and multiple = 1.
- Double: temp becomes 6 (multiple = 2), then 12 (multiple = 4), then 24 (multiple = 8).
- Next doubling gives 48, which is greater than 43.
- Subtract 24 from 43 → remaining dividend = 19.
- Add 8 to the quotient.
- Iteration 2:
- With remaining dividend = 19, start again: temp = 3, multiple = 1.
- Double: temp becomes 6 (multiple = 2), then 12 (multiple = 4).
- Next doubling gives 24, which is greater than 19.
- Subtract 12 from 19 → remaining dividend = 7.
- Add 4 to the quotient.
- Iteration 3:
- With remaining dividend = 7, start: temp = 3, multiple = 1.
- Double: temp becomes 6 (multiple = 2).
- Next doubling gives 12, which is greater than 7.
- Subtract 6 from 7 → remaining dividend = 1.
- Add 2 to the quotient.
- The loop ends as 1 is less than 3.
- Total quotient = 8 + 4 + 2 = 14.
Common Mistakes
- Not Handling Overflow: Forgetting the special case when dividend is INT_MIN and divisor is -1.
- Incorrect Sign Handling: Not correctly determining the sign of the result using XOR.
- Using Forbidden Operators: Accidentally using multiplication, division, or modulo operators in the logic.
- Inefficient Subtraction: Using the brute force subtraction method without optimization, leading to timeouts.
Edge Cases
-
Dividend is 0: The result should be 0 regardless of the divisor (except when divisor is 0, but that case is ruled out by the constraints).
-
Divisor is 1 or -1: Make sure to handle these cases especially when dividend is at the extreme ends of the 32-bit range.
-
Overflow Case: When dividend = -2147483648 and divisor = -1, the result overflows and should return 2147483647.
Alternative Variations
-
Division with Remainder: Sometimes you might need to also return the remainder. The algorithm can be extended to also compute dividend - (quotient * divisor) without using the multiplication operator.
-
Recursive Implementation: The doubling approach can also be implemented recursively for those who prefer recursion.
-
Generalized Bit Manipulation Problems: This problem is similar in concept to other bit manipulation tasks, such as implementing multiplication using addition and bit shifting.
Related Problems
GET YOUR FREE
Coding Questions Catalog
