Divide Two Integers

Question

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution

這題一開始在思考的時候，感覺沒有什麼特別的算法，想到用 loop 一直往上加，最終會算出答案，想當然爾，這樣得到的就是 TLE。再來就是 corner cases 處理起來特別麻煩，要考慮每個 input 都有可能 overflow，除了最大最小值外，除了之後最小值可能會變最大值。

解答看完後，有幾個重點要特別注意：

1. 記得先從 int 換成 long 來避免 overflow
2. 可以用一個 int sign = 1 來記錄正負號，最後把 ans * sign 就可以
3. 要寫個 longDivideHelper，裡面讓數字是 2 -> 4 -> 8 -> 16 -> 2ⁿ。但由於這樣做，有可能剩下的數還是會大於 divisor，譬如 11 除以 3，3+3 = 6，再下一個 6+6 > 11 了，此時會留下 5，所以在這個 longDivideHelper 裡面要用 recursion 去計算餘數

Code

class Solution {
    private long longDivideHelper(long dividend, long divisor) {
        if (dividend < divisor) {
            return 0;
        }

        long sum = divisor;
        long multiple = 1;
        while (sum + sum <= dividend) {
            sum += sum;
            multiple += multiple;
        }

        return multiple + longDivideHelper(dividend - sum, divisor);
    }
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { 
            sign = -1;
        }

        long longDividend = Math.abs((long)dividend);
        long longDivisor = Math.abs((long)divisor);

        if (longDivisor == 0) {
            return Integer.MAX_VALUE;
        }

        if (longDividend == 0 || longDividend < longDivisor) {
            return 0;
        }

        long lans = longDivideHelper(longDividend, longDivisor);
        int ans;

        if (lans > Integer.MAX_VALUE) {
            ans = (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        } else {
            ans = (int) (sign * lans);
        }
        return ans;
    }
}