029.Divide Two Integers

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
2
5
3
0
1
-2147483648
-1
-2147483648
-2147483648
-2147483648
5
-2147483648
-5

Solution 1: TLE

Brute force, TLE with no doubt.

Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int divide(int dividend, int divisor) {
    if (divisor == 0) 
        throw new ArithmeticException("/zero");
    if (dividend == 0) 
        return 0;
    if (dividend == Integer.MIN_VALUE && divisor == -1)
        return Integer.MAX_VALUE;
    int result = 0;
    int sign = -1;
    if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))
        sign = 1;
    long ldividend = Math.abs((long) dividend);
    long ldivisor = Math.abs((long) divisor);
    if (ldividend < ldivisor) 
        return 0;    
    while (ldividend >= ldivisor) {
        ldividend -= ldivisor;
        result++;
    }
    return sign * result;      
}

Solution 2: accepted 38ms 72.8%

Double the base if we can, decrease the time complexity to approximately logn.

Time: O(logn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int divide(int dividend, int divisor) {
    if (divisor == 0) 
        throw new ArithmeticException("/zero");
    if (dividend == 0) 
        return 0;
    if (dividend == Integer.MIN_VALUE && divisor == -1) // the only overflow case
        return Integer.MAX_VALUE;
    int result = 0;
    int factor = 1;
    int sign = -1;
    if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))
        sign = 1;
    long ldividend = Math.abs((long) dividend); // change to long and consider only positive side, making it easier  
    long ldivisor = Math.abs((long) divisor);
    if (ldividend < ldivisor) 
        return 0;    
    while (ldividend >= ldivisor) { 
        long temp = ldivisor;
        while (ldividend >= ldivisor + ldivisor) {  // double the divisor as much as we can
            ldivisor += ldivisor;
            ldividend -= ldivisor;
            factor += factor;
            result += factor;
        }
        ldivisor = temp;
        factor = 1;
        if (ldividend < ldivisor + ldivisor && ldividend >= ldivisor) { // deal with leftovers
            ldividend -= ldivisor;
            result++;
        }
    }
    return sign * result;      
}