CONY的世界

 29. Divide Two Integers

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

If it is overflow, return MAX_INT.

一開始想說先用個array 來記錄所有division的倍數，然後逐漸遞減下來

想法大概是 17/4  (13=8+4+1)

但是這種作法太花時間了 time exceeed 

所以就改成一般做除法的方式，把dividend 轉成string然後一個digit一個digit讀，然後看什麼時候比divisor後相減

要特別注意的地方是input 是integer 可能會overflow ，而integer的overflow 有點麻煩正數和負數其實你不知道會是哪個，就算加絕對值也沒用

所以這邊的做法是直接變成long來處理

class Solution {
    public int divide(int dividend, int divisor) {
        long result = div((long)dividend, (long)divisor);
        return (result>=Integer.MAX_VALUE)?Integer.MAX_VALUE:(result<Integer.MIN_VALUE)?Integer.MIN_VALUE:(int)result;
    }
    public long div(long dividend, long divisor) {
        boolean neg = (dividend<0)^(divisor<0);
        divisor = (divisor<0)?-divisor:divisor;        
        dividend = (dividend<0)?-dividend:dividend;
        String d=Long.toString(dividend);
        String result = new String();
        int l=0,r=1;
        long value = 0;
        while(r<=d.length()) {
            if(Long.parseLong(Long.toString(value)+d.substring(l,r)) >= divisor){
                int sum=0;
                value = Long.parseLong(Long.toString(value)+d.substring(l,r));
                while(value >= divisor) {
                    value-=divisor;
                    sum += 1;   
                }
                result += Integer.toString(sum);
                l=(r++);
            } else {
                r++;
                result+="0";
            }
        }
        return (neg)?-Long.parseLong(result):Long.parseLong(result);
    }
}