grid47 Exploring patterns and algorithms
Nov 4, 2024
6 min read
Solution to LeetCode 29: Divide Two Integers Problem
Given two integers dividend and divisor, divide dividend by divisor without using multiplication, division, or modulus operators. Truncate the result towards zero and return the quotient.
Problem
Approach
Steps
Complexity
Input: The input consists of two integers `dividend` and `divisor`.
Example: For example, `dividend = 15`, `divisor = 4`.
Constraints:
• -2^31 <= dividend, divisor <= 2^31 - 1
• divisor != 0
Output: Return the quotient after dividing `dividend` by `divisor`. The result should be truncated toward zero.
Example: For `dividend = 15`, `divisor = 4`, the output is `3`.
Constraints:
• The result should be within the 32-bit signed integer range: [-2^31, 2^31 - 1].
Goal: Divide the `dividend` by `divisor` without using multiplication, division, or modulus operators, and truncate the result toward zero.
Steps:
• Handle edge case where the dividend is INT_MIN and divisor is -1 to prevent overflow.
• Use bit manipulation (shifting) to simulate the division process and determine the quotient.
• Calculate the sign of the result based on the signs of the `dividend` and `divisor`.
• Iterate, doubling the divisor (using left shift) to subtract from the dividend in large chunks to optimize the division process.
Goal: The input consists of two integers `dividend` and `divisor`, and the result must be within the 32-bit signed integer range.
Steps:
• The `dividend` and `divisor` must be integers within the range [-2^31, 2^31 - 1].
• The `divisor` cannot be zero.
Assumptions:
• Both the `dividend` and `divisor` are valid 32-bit integers.
• The result must be truncated toward zero.
• Input: For `dividend = 15`, `divisor = 4`
• Explanation: The division of `15` by `4` results in `3.75`. Truncated toward zero, the result is `3`.
• Input: For `dividend = 10`, `divisor = -3`
• Explanation: The division of `10` by `-3` results in `-3.33333...`. Truncated toward zero, the result is `-3`.
Approach: The approach is to simulate the division operation using bit shifts. This avoids using multiplication, division, or modulus operators and allows us to compute the quotient efficiently.
Observations:
• The division can be optimized using bit shifts, which effectively doubles the divisor in each iteration, enabling fast subtraction from the dividend.
• We can use bitwise operations to speed up the division process and avoid expensive division or multiplication operations.
Steps:
• Check for edge case where the result may overflow (INT_MIN / -1).
• Use the absolute values of the dividend and divisor to simplify the logic.
• Iterate by left-shifting the divisor (doubling it) and subtracting from the dividend to reduce the dividend faster.
• Accumulate the quotient by adding the corresponding multiples of the divisor.
Empty Inputs:
• This problem will not encounter empty inputs as the `dividend` and `divisor` are always provided.
Large Inputs:
• Ensure that the solution handles large values of `dividend` and `divisor` efficiently.
Special Values:
• Handle the case where the `dividend` is `INT_MIN` and the `divisor` is `-1`, as it could lead to overflow.
Constraints:
• Ensure that the result is always within the 32-bit signed integer range.
intdivide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor ==-1) return INT_MAX;
long dvd = labs(dividend), dvs = labs(divisor);
int sgn = (dividend >0) ^ (divisor >0) ?-1:1;
long ans =0;
while( dvd >= dvs ) {
long tmp = dvs, m =1;
while(tmp <<1<= dvd) {
tmp <<=1;
m <<=1;
}
dvd -= tmp;
ans += m;
}
return sgn * ans;
}
1 : Function Declaration
intdivide(int dividend, int divisor) {
This line declares a function named 'divide' that takes two integer arguments: 'dividend' and 'divisor', and returns an integer representing the result of integer division.
2 : Edge Case Handling
if (dividend == INT_MIN && divisor ==-1) return INT_MAX;
This line handles a special edge case: when the dividend is the minimum integer value and the divisor is -1. In this case, the result would overflow, so the function returns the maximum integer value.
3 : Variable Initialization
long dvd = labs(dividend), dvs = labs(divisor);
This line converts both the dividend and divisor to long integers to avoid integer overflow during calculations. The `labs` function is used to get the absolute values of the operands.
4 : Variable Initialization
int sgn = (dividend >0) ^ (divisor >0) ?-1:1;
This line calculates the sign of the result. The `^` operator is used for XOR operation to determine the sign based on the signs of the dividend and divisor.
5 : Variable Initialization
long ans =0;
This line initializes a variable 'ans' to store the calculated quotient.
6 : Loop Iteration
while( dvd >= dvs ) {
This line starts a loop that continues as long as the dividend is greater than or equal to the divisor.
7 : Variable Initialization
long tmp = dvs, m =1;
This line initializes two temporary variables: 'tmp' to store the current divisor and 'm' to track the multiplier.
8 : Loop Iteration
while(tmp <<1<= dvd) {
This inner loop repeatedly doubles the 'tmp' and 'm' values as long as doubling 'tmp' does not exceed the dividend.
9 : Bitwise Operations
tmp <<=1;
This line left-shifts 'tmp' by 1, effectively doubling its value.
10 : Bitwise Operations
m <<=1;
This line left-shifts 'm' by 1, doubling its value as well.
11 : Mathematical Operations
dvd -= tmp;
This line subtracts the doubled 'tmp' value from the dividend.
12 : Result Update
ans += m;
This line adds the doubled 'm' value to the 'ans', effectively adding the number of times the doubled divisor can be subtracted from the dividend.
13 : Return
return sgn * ans;
After the loop, the 'ans' variable holds the quotient. The function returns the quotient multiplied by the sign determined earlier.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: The time complexity is O(log n) since the divisor is doubled in each iteration, reducing the dividend quickly.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only use a constant amount of space for variables.
