Sponsored
Sponsored
This approach uses repeated subtraction to calculate the quotient. The idea is to keep subtracting the divisor from the dividend until the dividend
Time Complexity: O(n), where n is the result of the division. This can be inefficient for large numbers.
Space Complexity: O(1), as no extra space is used.
1class Solution:
2 def divide(self, dividend: int, divisor: int) -> int:
3 if divisor == 0:
4 return 2**31 - 1
5 if dividend == -2**31 and divisor == -1:
6 return 2**31 - 1
7 sign = -1 if (dividend < 0) != (divisor < 0) else 1
8 dividend, divisor = abs(dividend), abs(divisor)
9 quotient = 0
10 while dividend >= divisor:
11 dividend -= divisor
12 quotient += 1
13 return sign * quotientPython's solution employs a class-based implementation, handling edge cases up front. Signs are assessed using tuple unpacking and conditional logic.
Computations use while loops to repeatedly subtract the divisor from the dividend and incrementally add to the quotient until the dividend is less than the divisor.
Bit manipulation provides an optimized method to divide without causing repeated subtractions. By efficiently finding how many times the divisor can be shifted left (multiplied by two) in the dividend range, we can ascertain parts of the quotient to sum incrementally. This halves the number of operations compared to repeated subtraction.
Time Complexity: O(log n), where n is the approximate number of bits in the dividend with respect to bit manipulation.
Space Complexity: O(1), as shifts occur without additional structures.
1
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
long long ldividend = std::abs((long long) dividend);
long long ldivisor = std::abs((long long) divisor);
int result = 0;
for (int i = 31; i >= 0; i--) {
if ((ldividend >> i) >= ldivisor) {
ldividend -= (ldivisor << i);
result += (1 << i);
}
}
return ((dividend < 0) ^ (divisor < 0)) ? -result : result;
}The approach implemented in C++ is similar to the C language's direction, using std::abs() to prevent inadvertent overflow, and the loop considers standout bit segment actions wherever divisor computations allow deductions to minimize iterations efficiently.