Leetcode 29. Divide Two Integers

Problem Explanation

This problem is asking us to perform division of two given integers without using the built-in multiplication, division and modulus operators in programming languages. Also, if the result from negative division is a fraction, we need to truncate it towards zero.

For example, given the input (dividend = 10, divisor = 3), the output should be 3. Here, 10 divides 3 times by 3, which leaves 1 as remainder but since we are to truncate it to the nearest integer towards zero, we get 3 as quotient.

Now, the challenging part of this problem is how to perform the division operation without using division or multiplication operators.

The solution provided above uses bitwise operations to solve this problem. Let's discuss the approach used by the solution.

Solution Approach

The approach to the solution involves using the technique of shifting bits to perform division operation. The idea is that we keep shifting (multiplying the divisor by 2) until it is less than the dividend, and then we subtract the divisor from the dividend. The number of times we could shift (double the divisor) until it is less than dividend is actually the quotient of the division.

For example, let's take dividend as 16 and divisor as 3.

Initial dividend = 16, divisor = 3, quotient = 0

• Multiply divisor by 2 (Shift divisor left by 1), divisor => 6, times_shifted => 1. Now 6 is less than 16, we continue
• Shift divisor left by 1 (i.e., multiply by 2), divisor => 12, times_shifted => 2. Now 12 is less than 16, we continue
• Shift divisor left by 1, divisor => 24, times_shifted => 4. Now 24 is greater than 16 so we stop shifting and update our dividend and quotient
• Subtract initial divisor * times_shifted from the dividend, dividend => 16 - (3 * 2) => 10.
• Add times_shifted to the quotient, quotient => 0 + 2 => 2.

Now, we continue this process until the dividend is >= divisor.

The solution also takes care of the overflow condition by checking it at the start.

Python Solution

Here is the same solution implemented in Python:

1
2python
3class Solution:
4    def divide(self, dividend: int, divisor: int) -> int:
5        if dividend == -2147483648 and divisor == -1:
6            return 2147483647
7        
8        dvd, dvs, res = abs(dividend), abs(divisor), 0
9        
10        while dvd >= dvs:
11            tmp, i = dvs, 1
12            while dvd >= tmp:
13                dvd -= tmp
14                res += i
15                i <<= 1
16                tmp <<= 1
17                
18        if (dividend > 0) == (divisor > 0):
19            return res
20        else:
21            return ~res + 1

Java Solution

Now let's implement the same solution in Java code:

1
2java
3class Solution {
4    public int divide(int dividend, int divisor) {
5        if (dividend == Integer.MIN_VALUE && divisor == -1) {
6            return Integer.MAX_VALUE;
7        }
8        
9        int a = Math.abs(dividend), b = Math.abs(divisor), res = 0;
10        
11        for (int x = 31; x >= 0; x--) {
12            if ((a >>> x) - b >= 0) {
13                res += 1 << x;
14                a -= b << x;
15            }
16        }
17        return (dividend > 0) == (divisor > 0) ? res : -res;
18    }
19}

JavaScript Solution

And here's the solution in JavaScript:

1
2javascript
3var divide = function(dividend, divisor) {
4    if (dividend === -2147483648 && divisor === -1) {
5        return 2147483647;
6    }
7    
8    var dvd = Math.abs(dividend), dvs = Math.abs(divisor), ans = 0;
9    
10    for (var i = 31; i >= 0; i--) {
11        if ((dvd >>> i) - dvs >= 0) {
12            ans += 1 << i;
13            dvd -= dvs << i;
14        }
15    }
16    return (dividend > 0) === (divisor > 0) ? ans : -ans;
17}

C++ Solution

Finally, here's the solution in C++:

1
2cpp
3class Solution {
4public:
5    int divide(int dividend, int divisor) {
6        if (dividend == INT_MIN && divisor == -1) {
7            return INT_MAX;
8        }
9        
10        int a = abs(dividend), b = abs(divisor), res = 0;
11        
12        for (int x = 31; x >= 0; x--) {
13            if ((a >> x) - b >= 0) {
14                res += 1 << x;
15                a -= b << x;
16            }
17        }
18        return (dividend > 0) == (divisor > 0) ? res : -res;
19    }
20};

C# Solution

Here's the solution in C#:

1
2csharp
3public class Solution {
4    public int Divide(int dividend, int divisor) {
5        if (dividend == Int32.MinValue && divisor == -1) {
6            return Int32.MaxValue;
7        }
8        
9        long dvd = Math.Abs((long)dividend), dvs = Math.Abs((long)divisor), ans = 0;
10        
11        for (int i = 31; i >= 0; i--) {
12            if ((dvd >> i) - dvs >= 0) {
13                ans += 1 << i;
14                dvd -= dvs << i;
15            }
16        }
17        return ((dividend > 0) == (divisor > 0)) ? (int)ans : -(int)ans;
18    }
19}

Note: Since we're dealing with 32-bit signed integers, we need to handle overflow situations properly. For example, -2^{31} / -1 = 2^31, which is an overflow. We return 2^31 - 1 in such cases.## Implications & Complexity

The bit manipulation approach above is quite efficient. It saves computation by testing the dividend against multiple of divisor instead of testing one by one. It finds the largest multiple of divisor and subtracts that from the dividend then repeats the process with the resulting new dividend.

The time complexity of this approach is O(log N), where N is the dividend. This is due to the loop which runs maximum 32 times, because int operates with 32 bits. Thus, we can say that the running time complexity is proportional to the number of bits used by the dividend.

The space complexity of this approach is O(1), as we are using a constant amount of extra space.

Golang Solution

Below is an implementation of the same method using Go language.

1
2go
3import "math"
4
5func divide(dividend int, divisor int) int {
6    if dividend == math.MinInt32 && divisor == -1 {
7        return math.MaxInt32
8    }
9    
10    res := 0
11    a := abs(dividend)
12    b := abs(divisor)
13    
14    for i := 31; i >= 0; i-- {
15        if a>>uint(i) >= b {
16            n := a >> uint(i)
17            res += n
18            a -= b * n
19        }
20    }
21    
22    if (dividend > 0) == (divisor > 0) {
23        return res
24    }
25    return -res
26}
27
28func abs(a int) int {
29    if a > 0 {
30        return a
31    }
32    return -a
33}

To summarize, the algorithm above uses bit manipulation to solve this problem and avoids overflow by working with the absolute value of the inputs. It works in constant space and takes logarithmic time to execute. Therefore, it is a very efficient solution to the problem of dividing two integers without using the division and multiplication operators.