DivideTwoIntegers [source code]

public class DivideTwoIntegers {
static
/******************************************************************************/
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1 || divisor == 0)
            return Integer.MAX_VALUE;
        if (divisor == 1)
            return dividend;
        if (divisor == 2)
            return dividend >> 1;
        boolean neg = dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0;
        // Tricky: ABS funciton might betray you, MIN_VALUE has to be handled separately
        int dividend_abs = dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs (dividend);
        int divisor_abs = divisor == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs (divisor);
        if (divisor_abs > dividend_abs || dividend == Integer.MAX_VALUE && divisor == Integer.MIN_VALUE)
            return 0;
        int lo = 0, hi = dividend_abs, power = 0;
        while (lo < hi) {
            int mid = lo + (hi - lo) >> 1;
            power++;
            if (mid >= divisor_abs)
                hi = mid;
            else break;
        }
        long sum_lo = divisor_abs << (power - 1), sum_hi = divisor_abs << power, sum = sum_lo, res = (1 << (power - 1)) - 1;
        while (sum <= dividend_abs) {
            sum += divisor_abs;
            res++;
        }
        return (int) (neg ? -res : res);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        DivideTwoIntegers.Solution tester = new DivideTwoIntegers.Solution();
        int[] inputs = {
            10, 3, 3,
            9, 3, 3,
            12, 3, 4,
            13, 3, 4,
            1, -1, -1,
            2147483647, 3, 715827882,
            -2147483648, -3, 715827882,
            -1010369383, -2147483648, 0, 
            2147483647, -2147483648, 0,
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int dividend = inputs[3 * i], divisor = inputs[3 * i + 1], ans = inputs[3 * i + 2];
            System.out.println (Printer.separator ());
            int output = tester.divide (dividend, divisor);
            System.out.printf ("%d and %d -> %s, expected: %d\n", 
                dividend, divisor, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

应该是有什么数序解法的; 这个题目downvote特别多, 估计就跟这个有关系; 不过还是自己先用笨办法写写看;

题目给了一个信息, overflow, 仔细想想, 什么情况下会overflow? 只有除数为0的情况下吗?

最后大概写了这个算法:

class Solution {  
    public int divide(int dividend, int divisor) {  
        if (dividend == Integer.MIN_VALUE && divisor == -1 || divisor == 0)  
            return Integer.MAX_VALUE;  
        if (divisor == 1)  
            return dividend;  
        if (divisor == 2)  
            return dividend >> 1;  
        boolean neg = dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0;  
        dividend = Math.abs (dividend);  
        divisor = Math.abs (divisor);  
        if (divisor > dividend)  
            return 0;  
        int res = 0, sum = divisor;  
        while (sum <= dividend) {  
            sum += divisor;  
            res++;  
        }  
        return neg ? -res : res;  
    }  
}

最后这个算法还是TLE了, 能加的优化都加了, 没办法了; 所以说难怪这个题目被喷的厉害, 最后确实是只有数学解法能AC; 不过就算是这个naive的解法, 写的时候还是要注意, 比如最后返回的到底是res还是res+1? 这个如果搞不清, 找个例子跑一遍iteration head trace就行了;

tag给了binary search的提示, 往这个方向想, 举了个例子, 还是没思路;

好像大概有一个近似的思路; 不行, 尝试了一下, 我的思路是, 直接用binary search, 先找到, 比如10/3, 我找到2和4, 分别是2的power, 写一个binary search可以找到最近的两个power点;

最后好歹是AC了, 速度是230ms (1%), 所以应该是有更好的办法; 不过这个算法写起来并不简单, 被各种各样的case break; 总体思路上注意一个问题, 我这里是先用dividend除2的power, 然后得到一个数和divisor比, 注意, 这里有一个大坑:

java> 2147483647 / 3  
java.lang.Integer res5 = 715827882  
java> 2147483647 >> 29  
java.lang.Integer res6 = 3  
java> 1 << 29  
java.lang.Integer res7 = 536870912  
java> 2147483647 / 536870912  
java.lang.Integer res8 = 3  
java> 2147483647 / 715827882  
java.lang.Integer res9 = 3

你看这里, 你除1^29出来等于3, 但是你除3实际上不等于1^29! 另外, 注意这里Binary Search的写法, 用的是开区间写法, 因为我在里面的更新hi的时候不想要-1: 我要的是不停的/2, 所以-1之后的偏移或许会导致问题? 反正感觉不太稳;

另外, if (mid >= divisor_abs) 这里要包含这个等号; 还是看上面这个例子, 2147483647 / (2^29) = 3, 但是这个是因为truncation的结果, 实际上, 2147483647 / (2^29) >= 3, 那么3 (2^29) <= 2147483647. 我们要用3 2^power来作为上限, 他要比2147483647大, 但是这里明显, 29是不够的, 所以在等号的时候, 要多除一次;

反正我这个做法的思路还是稍微变换了一下思路, 不让用divide, 就用divide by 2, which is just shift.

没有editorial;

@jianchao.li.fighter said in Detailed Explained 8ms C++ solution:

In this problem, we are asked to divide two integers. However, we are not allowed to use division, multiplication and mod operations. So, what else can we use? Yeah, bit manipulations.

Let's do an example and see how bit manipulations work.

Suppose we want to divide 15 by 3, so 15 is dividend and 3 is divisor. Well, division simply requires us to find how many times we can subtract the divisor from the the dividend without making the dividend negative.

Let's get started. We subtract 3 from 15 and we get 12, which is positive. Let's try to subtract more. Well, we shift 3 to the left by 1 bit and we get 6. Subtracting 6 from 15 still gives a positive result. Well, we shift again and get 12. We subtract 12 from 15 and it is still positive. We shift again, obtaining 24 and we know we can at most subtract 12. Well, since 12 is obtained by shifting 3 to left twice, we know it is 4 times of 3. How do we obtain this 4? Well, we start from 1 and shift it to left twice at the same time. We add 4 to an answer (initialized to be 0). In fact, the above process is like 15 = 3 * 4 + 3. We now get part of the quotient (4), with a remainder 3.

Then we repeat the above process again. We subtract divisor = 3 from the remaining dividend = 3 and obtain 0. We know we are done. No shift happens, so we simply add 1 << 0 to the answer.

Now we have the full algorithm to perform division.

According to the problem statement, we need to handle some exceptions, such as overflow.

Well, two cases may cause overflow:

1. divisor = 0;
2. dividend = INT_MIN and divisor = -1 (because abs(INT_MIN) = INT_MAX + 1).

Of course, we also need to take the sign into considerations, which is relatively easy.

Putting all these together, we have the following code.

class Solution {  
public:  
    int divide(int dividend, int divisor) {  
        if (!divisor || (dividend == INT_MIN && divisor == -1))  
            return INT_MAX;  
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;  
        long long dvd = labs(dividend);  
        long long dvs = labs(divisor);  
        int res = 0;  
        while (dvd >= dvs) {   
            long long temp = dvs, multiple = 1;  
            while (dvd >= (temp << 1)) {  
                temp <<= 1;  
                multiple <<= 1;  
            }  
            dvd -= temp;  
            res += multiple;  
        }  
        return sign == 1 ? res : -res;   
    }  
};

算法一开始没有看懂, 用20, 3这个例子trace了一下, 还是理解了, 这个算法还是比较ad-hoc的, 也不知道怎么解说, 反正就是按照2的倍数的操作不停的subtract; 我的算法跟他的算法比起来, 速度太慢了, 主要原因可能...我也不知道是什么原因. 其实我的算法并没有做到他这里的insight, 我是找到最近的两个power of 2的点之后, 剩下的部分还是穷搜的, 所以最坏情况下, 搜的距离其实也不少; 他这个是什么思想?

感觉是一个类似every number can be sum of power of 2的思想? 是对的, 没错, 因为比如你20/3, 你最后得到的其实是想知道20里面有多少个3, 假设有x个, 那么这个x是可以拆分成为sum of power of 2的; 这里用的我感觉就是这个核心的insight;

另外注意他这里提取sign的操作方法, 用的xor, 不过好像java里面没有办法这么方便的写出来; 不对, 可以的, java的boolean之间是有xor操作的;

@liji94188 said in Detailed Explained 8ms C++ solution:

great idea! but I think we should not use long (what if they give you two long input?) since it's a int problem. Here is how I handle the dividend == Integer.MIN_VALUE case:

public class Solution {>   
    public int divide(int dividend, int divisor) {  
        //other code...  
        if(dividend==Integer.MIN_VALUE){  
            if(divisor==-1) return Integer.MAX_VALUE;  
            else if(divisor==1)  return dividend;  
            else return ((divisor&1)==1)?divide(dividend+1,divisor):divide(dividend>>1,divisor>>1);  
        }   
        if(divisor==Integer.MIN_VALUE) return 0;  
        //other code continue...  
    }  
}

Hope will make sense :)

这个理解不通了, 这个的作者并没有给出这个做法的理由, OP则说, 反正是dividend是MIN_VALUE的情况, 所以自己试一试就知道了; 但是他这个解释太肤浅了, 他这个只是在阐述正确性, 不过你一开始是怎么意识到要根据奇偶性分开对待? 这个就没有解释;

自己试了一下, 在这个java版本的基础上:

class Solution {  
public:  
    int divide(int dividend, int divisor) {  
        if (!divisor || (dividend == INT_MIN && divisor == -1))  
            return INT_MAX;  
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;  
        long long dvd = labs(dividend);  
        long long dvs = labs(divisor);  
        int res = 0;  
        while (dvd >= dvs) {   
            long long temp = dvs, multiple = 1;  
            while (dvd >= (temp << 1)) {  
                temp <<= 1;  
                multiple <<= 1;  
            }  
            dvd -= temp;  
            res += multiple;  
        }  
        return sign == 1 ? res : -res;   
    }  
};

最后发现第三种情况直接改成divide(dividend+1,divisor)还是真的不行的, 就是要区分奇偶性;

另外一个处理MIN导致的overflow的做法:

public class Solution {  
    public int divide(int dividend, int divisor) {  
        int over = 0;  
        if(dividend == Integer.MIN_VALUE){  
            if(divisor == -1){  
                return Integer.MAX_VALUE;  
            }  
            else if(divisor == 1){  
                return dividend;  
            }  
            else if(divisor == Integer.MIN_VALUE){  
                return 1;  
            }  
            else{  
                over = 1;  
            }  

        }  

        if(divisor == Integer.MIN_VALUE){  
            return 0;  
        }  
        else{  
            int flag = 1;  
            if((divisor < 0 && dividend > 0) || (divisor > 0 && dividend < 0) ){  
                flag = -1;  
            }  
            divisor = Math.abs(divisor);  
            dividend = Math.abs(dividend + over);  

            int result = 0;  
            while(dividend >= divisor){  
                int power = divisor;  
                int mul = 1;  
                while(dividend > power){  
                    int temp = power;  
                    power <<= 1;  
                    if((power >> 1) != temp){  
                        power = temp;  
                        break;  
                    }  
                    else{  
                        mul <<= 1;  
                    }  
                }  
                if(dividend < power){  
                    mul >>= 1;  
                    power >>= 1;  
                }  

                result += mul;  
                dividend -= power;  
                dividend += over;  
                over = 0;  
            }  
            return result * flag;  
        }  
    }  
}

大概看了一下这个人的思路, 基本就是一开始先把MIN超MAX的那个1给拿出来藏起来, 然后等到第一轮subtract结束之后, 再补回去. 一个有点想法的小操作;

下面有一个用recursion写的方法:

@jaqenhgar said in Detailed Explained 8ms C++ solution:

My approach is that you keep subtracting divisor, and double it each time while keeping track of the how many times it doubled. If doubling goes above dividend, then divide by 2 and try again.

    public int divide(int a, int b) {  
        if(a==Integer.MIN_VALUE){  
            if(b==-1) return Integer.MAX_VALUE;  
        }  

        long x = a < 0 ? -(long)a : (long)a;  
        long y = b < 0 ? -(long)b : (long)b;  

        int res = recurse(x, y, 1);  
        if(a < 0 && b < 0) return res;  
        if(a < 0 || b < 0) return -res;  
        return res;  
    }  

    public int recurse(long x, long y, int count) {  
        if(x <= 0 || count==0) return 0;  
        if(y > x) return recurse(x, y >>> 1, count >>> 1); //overshot, so divide and try again.  
        else return recurse(x-y, y+y, count+count)+count;  
    }

有点复杂的, 画了一个20/3的trace之后才看懂; 感觉他这个逻辑写的有点故意太绕了, 尤其是这个base case怎么回事, 你在真的跑完一个trace之前完全是没有头绪的; 对了, 顺便提一下, 看很多算法, 包括recursion, base case这种明显是类似special handling的东西, 读算法第一遍的时候其实可以有条件的无视. 第一遍, 最重要的是读懂核心逻辑, 然后这些condition啊, base啊, 后面读第二遍的时候再考虑是处理什么的. 你该不会是指望一遍就读懂一个算法吧? 读算法的重点是揣摩, 别特么把自己当成一个interpreter了;

@jinwu said in Clean Java solution with some comment.:

  public int divide(int dividend, int divisor) {  
      //Reduce the problem to positive long integer to make it easier.  
      //Use long to avoid integer overflow cases.  
      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);  

      //Take care the edge cases.  
      if (ldivisor == 0) return Integer.MAX_VALUE;  
      if ((ldividend == 0) || (ldividend < ldivisor)) return 0;  

      long lans = ldivide(ldividend, ldivisor);  

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

  private long ldivide(long ldividend, long ldivisor) {  
      // Recursion exit condition  
      if (ldividend < ldivisor) return 0;  

      //  Find the largest multiple so that (divisor * multiple <= dividend),   
      //  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.  
      //  Think this as a binary search.  
      long sum = ldivisor;  
      long multiple = 1;  
      while ((sum+sum) <= ldividend) {  
          sum += sum;  
          multiple += multiple;  
      }  
      //Look for additional value for the multiple from the reminder (dividend - sum) recursively.  
      return multiple + ldivide(ldividend - sum, ldivisor);  
  }

这个就是相对直观的一个recursion改写了, 没有上面那个那么复杂;

后面看到的大部分算法, 都是直接用long来处理overflow了; 第一个解法那里那个判断奇偶性的感觉还是太秀了, 真正面试的时候我感觉基本能掌握用long处理就可以了, 不要给自己加戏;

这个是一个带秀的解法:

@zjupure said in 32 times bit shift operation in C with O(1) solution:

we assure the factor ret's binary fomula is

ret = a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31; ai = 0 or 1, i = 0......31

the dividend B and divisor A is non-negative, then

A(a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31) = B; Eq1

(1) when Eq1 divided by 2^31, we can get A*a31 = B>>31; then a31 = (B>>31)/A;

if (B>>31) > A, then a31 = 1; else a31 = 0;

(2) when Eq1 divided by 2^30, we can get A*a30 + A*a30*2 = B>>30; then a30 = ((B>>30) - a30*A*2)/A; and (B>>30) - a31*A*2 can be rewritten by (B-a31*A<<31)>>30, so we make B' = B-a31*A<<31, the formula simplified to a30 = (B'>>30)/A

if (B'>>31) > A, then a30 = 1; else a30 = 0;

(3) in the same reason, we can get a29 = ((B-a31*A<<31-a30*A<<30)>>29)/A, we make B'' = B' - a30*A<<30, the formula simplified to a29 = (B''>>29)/A;

do the same bit operation 32 times, we can get a31 ..... a0, so we get the ret finally.

the C solution with constant time complexity

    int divide(int dividend, int divisor) {  
        //special cases  
        if(divisor == 0 || (dividend == INT_MIN && divisor == -1))  
            return INT_MAX;  

        // transform to unsigned int  
        bool sign = (dividend > 0)^(divisor > 0);  
        unsigned int A = (divisor < 0) ? -divisor : divisor;  
        unsigned int B = (dividend < 0) ? -dividend : dividend;  
        int ret = 0;  

        // shift 32 times  
        for(int i = 31; i >= 0; i--)  
        {  
            if((B>>i) >= A)  
            {  
                ret = (ret<<1)|0x01;  
                B -= (A<<i);   // update B  
            }  
            else  
                ret = ret<<1;  
        }  

        if(sign)  
            ret = -ret;  

        return ret;  
    }

这个人的思路非常清晰, 而且真正实现的时候还用了一点技巧(维护一个累加和, 一直从B里面减掉). 非常带秀的一个解法;

submission最优解: 36(90):

class Solution {  
    public int divide(int dividend, int divisor) {  
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {  
            return Integer.MAX_VALUE;  
        }  
        long lDividend = Math.abs((long) dividend);  
        long lDivisor = Math.abs((long) divisor);  
        if (dividend == 0 || lDividend < lDivisor) {  
            return 0;  
        }  
        int q = 0;  
        boolean diffSign = false;  
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) {  
            diffSign = true;  
        }  
        while (lDividend >= lDivisor) {  
            long temp = lDivisor;  
            long multiplier = 1;  
            while (lDividend >= temp << 1) {  
                temp <<= 1;  
                multiplier <<= 1;  
            }  
            lDividend -= temp;  
            q += multiplier;  
        }  
        if (diffSign) {  
            return q * (-1);  
        } else {  
            return q;  
        }  

    }  
}

就是discussion最优解了;

Problem Description

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

If it is overflow, return MAX_INT.

Difficulty:Medium
Total Accepted:123.3K
Total Submissions:778.3K
Contributor:LeetCode
Related Topics
mathbinary search