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.
1public class Divider {
2 public int divide(int dividend, int divisor) {
3 if (divisor == 0) return Integer.MAX_VALUE;
4 if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
5 int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
6 long ldividend = Math.abs((long) dividend);
7 long ldivisor = Math.abs((long) divisor);
8 int quotient = 0;
9 while (ldividend >= ldivisor) {
10 ldividend -= ldivisor;
11 quotient++;
12 }
13 return sign * quotient;
14 }
15}The Java solution uses the long primitive type to avoid overflow while working with absolute values. It checks edge cases and handles sign computation similarly to the C/C++ solutions. The subtraction logic remains unchanged.
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.
1Java's bit manipulation method effectively uses long values with logical bit shifting operations. It starts with bit position examination decrement-wise, and successive confirmations allow the right subtraction of pre-multiplied equivalents.