[LeetCode][29. Divide Two Integers] 5 Approaches: Brute Force use Long, Brute Force use Int, Binary Search use Long, Binary Search use Int and Recursion

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 7k 阅读时长 ≈ 6 分钟

By Long Luo

This article is the solution 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int and Recursion of Problem 29. Divide Two Integers , Chinese version is 3种方法：暴力法，二分搜索，递归 .

Here shows 5 Approaches to slove this problem: Brute Force use \(\texttt{Long}\), Brute Force use \(\texttt{Int}\), Binary Search use \(\texttt{Long}\), Binary Search use \(\texttt{Int}\) and Recursion.

Intuition

To divide two integers without using multiplication, division, and mod operator, so we can subtract the \(\textit{divisor}\) from the \(\textit{dividend}\) util the \(\textit{result} \ge 0\).

Brute Force use Long

We can make the \(\textit{dividend}\) and \(\textit{divisor}\) positive, and cast to \(\texttt{long}\), then process.

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
public int divide(int dividend, int divisor) {
    if (dividend == 0) {
        return 0;
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

The solution will Time Limit Exceeded, we have to deal with some corner cases.

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
38
39
40
41
42
43
44
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }
    
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return Integer.MAX_VALUE;
        }
    } else if (dividend == Integer.MAX_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

Analysis

  • Time Complexity: \(O(x / y)\).
  • Space Complexity: \(O(1)\).

Brute Force use Int

Since the environment that could only store integers within the \(32-bit\) signed integer, so we have to deal with it.

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
38
39
40
41
42
43
44
45
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return dividend;
            } else if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        } else if (dividend == Integer.MAX_VALUE) {
            if (divisor == 1) {
                return dividend;
            } else if (divisor == -1) {
                return -dividend;
            }
        }

        int ans = 0;
        boolean sign = true;
        if (dividend > 0 && divisor > 0) {
            dividend = -dividend;
            sign = false;
        } else if (dividend > 0 && divisor < 0) {
            dividend = -dividend;
            divisor = -divisor;
        } else if (dividend < 0 && divisor < 0) {
            sign = false;
            divisor = -divisor;
        }

        while (dividend + divisor <= 0) {
            dividend += divisor;
            ans++;
        }

        return sign ? -ans : ans;
    }
}

Analysis

  • Time Complexity: \(O(x / y)\).
  • Space Complexity: \(O(1)\).

Binary Search use Long

Refer to Fast Power Algorithm: Binary Exponentiation , we can use the \(\texttt{quickAdd}\) like the \(\texttt{quickMul}\).

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int divide(int dividend, int divisor) {
        long x = dividend;
        long y = divisor;

        boolean sign = false;

        if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
            sign = true;
        }

        if (x < 0) {
            x = -x;
        }

        if (y < 0) {
            y = -y;
        }

        long left = 0;
        long right = x;

        while (left < right) {
            long mid = (left + right + 1) >> 1;
            long result = quickAdd(y, mid);
            if (result <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        long ans = sign ? -left : left;
        if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }

        return (int) ans;
    }

    public long quickAdd(long x, long y) {
        long ans = 0;
        while (y > 0) {
            if ((y & 0x01) == 1) {
                ans += x;
            }

            x += x;
            y = y >> 1;
        }

        return ans;
    }
}

Analysis

  • Time Complexity: \(O(logx \times logy)\).
  • Space Complexity: \(O(1)\).

Binary Search use Int

  1. the corner cases;
  2. Record the sign of the final result and turn both numbers to negative numbers;
  3. Approximate the \(\textit{divisor}\) by increasing the \(\textit{dividend}\) incrementally.
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            } else if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }

        boolean sign = false;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = true;
        }

        if (dividend > 0) {
            dividend = -dividend;
        }

        if (divisor > 0) {
            divisor = -divisor;
        }

        int MAX = Integer.MIN_VALUE >> 1;
        int ans = 0;

        // dividend became negative
        while (dividend <= divisor) {
            int temp = divisor;
            int step = -1;

            while (temp >= MAX && step >= MAX && temp >= dividend - temp) {
                temp += temp;
                step += step;
            }

            dividend -= temp;
            ans += step;
        }

        return sign ? ans : -ans;
    }
}

Analysis

  • Time Complexity: \(O(logx \times logy)\).
  • Space Complexity: \(O(1)\).

Recursion

The recurison method.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            } else if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }

        long x = dividend;
        long y = divisor;

        boolean sign = false;
        if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
            sign = true;
        }

        x = x > 0 ? x : -x;
        y = y > 0 ? y : -y;

        long ans = div(x, y);
        if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }

        return (int) (sign ? -ans : ans);
    }

    public long div(long dividend, long divisor) {
        if (dividend < divisor) {
            return 0;
        }

        long ans = 1;
        long temp = divisor;

        while ((temp + temp) <= dividend) {
            ans = ans << 1;
            temp = temp << 1;
        }

        return ans + div(dividend - temp, divisor);
    }
}

Analysis

  • Time Complexity: \(O(logx \times logy)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗