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.
1function divide(dividend, divisor) {
2 if (divisor === 0) return Number.MAX_SAFE_INTEGER;
3 if (dividend === -(2**31) && divisor === -1) return (2**31) - 1;
4 var sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
5 var ldividend = Math.abs(dividend);
6 var ldivisor = Math.abs(divisor);
7 var quotient = 0;
8 while (ldividend >= ldivisor) {
9 ldividend -= ldivisor;
10 quotient++;
11 }
12 return sign * quotient;
13}JavaScript's version calculates division similar to C-like approaches, checking for divisor zero, handling overflows, and using bitwise XOR for sign assessment. It uses a while loop to decrement the dividend while tracking how many times subtraction occurs until input conditions are satisfied.
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.
public int Divide(int dividend, int divisor) {
if (divisor == 0) return int.MaxValue;
if (dividend == int.MinValue && divisor == -1) return int.MaxValue;
long ldividend = Math.Abs((long)dividend);
long ldivisor = Math.Abs((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;
}
}C# implementation requires using Math.Abs() and long types due to language headroom limitations while computing division equivalents without direct fractional comparison. Bit operations gradually develop quotient parts based on power division within permissible value calculations.