Massive Algorithms: LeetCode 29 - Divide Two Integers

LeetCode 29 - Divide Two Integers

https://leetcode.com/problems/divide-two-integers/

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows

https://www.cnblogs.com/grandyang/p/4431949.html
这道题让我们求两数相除，而且规定我们不能用乘法，除法和取余操作，那么我们还可以用另一神器位操作Bit Operation，思路是，如果被除数大于或等于除数，则进行如下循环，定义变量t等于除数，定义计数p，当t的两倍小于等于被除数时，进行如下循环，t扩大一倍，p扩大一倍，然后更新res和m。这道题的OJ给的一些test case非常的讨厌，因为输入的都是int型，比如被除数是-2147483648，在int范围内，当除数是-1时，结果就超出了int范围，需要返回INT_MAX，所以对于这种情况我们就在开始用if判定，将其和除数为0的情况放一起判定，返回INT_MAX。然后我们还要根据被除数和除数的正负来确定返回值的正负，这里我们采用长整型long来完成所有的计算，最后返回值乘以符号即可

    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
        long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        if (n == 1) return sign == 1 ? m : -m;
        while (m >= n) {
            long long t = n, p = 1;
            while (m >= (t << 1)) {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        return sign == 1 ? res : -res;
    }

我们可以使上面的解法变得更加简洁：

    int divide(int dividend, int divisor) {
        long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
        if (m < n) return 0;    
        while (m >= n) {
            long long t = n, p = 1;
            while (m > (t << 1)) {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        if ((dividend < 0) ^ (divisor < 0)) res = -res;
        return res > INT_MAX ? INT_MAX : res;
    }

https://www.jianshu.com/p/92e1e04b1b98

https://leetcode.com/problems/divide-two-integers/discuss/13397/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);
}

https://leetcode.com/problems/divide-two-integers/discuss/13407/C%2B%2B-bit-manipulations

he key observation is that the quotient of a division is just the number of times that we can subtract the divisor from the dividend without making it negative.

Suppose dividend = 15 and divisor = 3, 15 - 3 > 0. We now try to subtract more by shifting 3 to the left by 1 bit (6). Since 15 - 6 > 0, shift 6 again to 12. Now 15 - 12 > 0, shift 12 again to 24, which is larger than 15. So we can at most subtract 12 from 15. Since 12 is obtained by shifting 3 to left twice, it is 1 << 2 = 4times of 3. We add 4 to an answer variable (initialized to be 0). The above process is like 15 = 3 * 4 + 3. We now get part of the quotient (4), with a remaining dividend 3.

Then we repeat the above process by subtracting divisor = 3 from the remaining dividend = 3 and obtain 0. We are done. In this case, no shift happens. We simply add 1 << 0 = 1 to the answer variable.

This is the full algorithm to perform division using bit manipulations. The sign also needs to be taken into consideration. And we still need to handle one overflow case: dividend = INT_MIN and divisor = -1.

    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        long dvd = labs(dividend), dvs = labs(divisor), ans = 0;
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
        while (dvd >= dvs) {
            long temp = dvs, m = 1;
            while (temp << 1 <= dvd) {
                temp <<= 1;
                m <<= 1;
            }
            dvd -= temp;
            ans += m;
        }
        return sign * ans;
    }

https://leetcode.com/problems/divide-two-integers/discuss/13467/Very-detailed-step-by-step-explanation-(Java-solution)

public int divide(int dividend, int divisor) {
    boolean isNegative = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ? true : false;
    long absDividend = Math.abs((long) dividend);
    long absDivisor = Math.abs((long) divisor);
    long result = 0;
    while(absDividend >= absDivisor){
        long tmp = absDivisor, count = 1;
        while(tmp <= absDividend){
            tmp <<= 1;
            count <<= 1;
        }
        result += count >> 1;
        absDividend -= tmp >> 1;
    }
    return  isNegative ? (int) ~result + 1 : result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result;
}

https://leetcode.com/discuss/38997/detailed-explained-8ms-c-solution

Well, two cases may cause overflow:

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

One thing needs to be mentioned is that we need to convert the integer to long type. Otherwise the Math.abs() value of Integer.MIN_VALUE will be quite strange.

    public int divide(int dividend, int divisor) {

        long p = Math.abs((long)dividend);

        long q = Math.abs((long)divisor);

        int ret = 0;

        while (p >= q) {

            int counter = 0;

            while (p >= (q << counter)) {

                counter++;

}

            ret += 1 << (counter - 1);

            p -= q << (counter - 1);

}

        if (dividend == Integer.MIN_VALUE && divisor == -1)

            return Integer.MAX_VALUE;

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))

            return ret;

        else

            return -ret;

}

Updated on March 7th, 2015. Add the following code to pass the corner case. Not sure if it is the best way.

1 2	if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

https://www.programcreek.com/2014/05/leetcode-divide-two-integers-java/

public int divide(int dividend, int divisor) {
    //handle special cases
    if(divisor==0) return Integer.MAX_VALUE; // throw ex;
    if(divisor==-1 && dividend == Integer.MIN_VALUE)
        return Integer.MAX_VALUE; // return min_value
 
    //get positive values
    long pDividend = Math.abs((long)dividend);
    long pDivisor = Math.abs((long)divisor);
 
    int result = 0;
    while(pDividend>=pDivisor){
        //calculate number of left shifts
        int numShift = 0;    
        while(pDividend>=(pDivisor<<numShift)){
            numShift++;
        }
 
        //dividend minus the largest shifted divisor
        result += 1<<(numShift-1);
        pDividend -= (pDivisor<<(numShift-1));
    }
 
    if((dividend>0 && divisor>0) || (dividend<0 && divisor<0)){
        return result;
    }else{
        return -result;
    }
}

http://wp.javayu.me/2014/02/divide-two-integers/

    int divide(int dividend, int divisor) {

        long long dv = abs((long long)dividend);

        long long ds = abs((long long)divisor);

        long long remain = dv;

        long long res = 0;

        while(remain >= ds)

{

            int sh = -1;

            long long v = remain;

            while (v >= ds)

{

                v >>= 1;

                sh++;

}

            remain -= ds << sh;

            res += 1 <<sh;

}

        if ((divisor > 0) != (dividend > 0))

            res = -res;

        return res;

}

dividend和divisor的符号。思考算法时默认它们都是正数，实际却并非如此，各种情况都需要考虑。为了应对这一问题，可以先对绝对值求结果，然后附上符号
int的绝对值，int里面有一个特殊的数字：-2147483648，它的绝对值或者相反数 2147483648是超出int的范围的，对于这一情况需要特殊处理。所以不能直接调用 divide(-dividend, divisor)或者divide(dividend, – divisor)。也不能写 int dv = abs(dividend)。处理方式是使用long long来保存其绝对值
计算绝对值的时候要写 long long dv = abs((long long)dividens)的原因是，abs()有两个重载版本，其中一个是abs(int)，另外一个是abs(long)，如果不进行显式转换，则调用abs(int)，对-2147483648的返回结果仍是-2147483648
计算两个整数商的时候，有两种选择：将被除数dv右移或者将除数ds右移，循环终止条件是dv < ds。以上代码选用了右移被除数dv。原因是：当dv最高位（除符号位外）为1时，左移ds可能因为小于dv而将ds的有效位从最左移出，既会使比较出错，也可能导致死循环。
最后，在return res这里，还是可能会出错的，但是就不在这段程序的考虑范围了，错误输入： -2147483648， -1
坑啊坑啊都是坑。long long是个好东西。

http://sbzhouhao.net/LeetCode/LeetCode-Divide-Two-Integers.html

    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {
            return Integer.MAX_VALUE;
        }
        if (divisor == 1) {
            return dividend;
        }
        if (dividend == 0) {
            return 0;
        }
        long l = Math.abs((long) dividend);
        long r = Math.abs((long) divisor);
        int result = 0;
        while (l >= r) {
            int count = 0;
            while (l >= (r << count)) {
                count++;
            }
            result += 1 << (count - 1);
            l -= r << (count - 1);
        }
        if (l == Integer.MAX_VALUE + 1L && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        return (dividend > 0 ^ divisor > 0) ? result * -1 : result;
    }

http://www.shuatiblog.com/blog/2014/05/10/Divide-Two-Integers/

X. Recursion
http://www.cnblogs.com/grandyang/p/4431949.html

    int divide(int dividend, int divisor) {
        long long res = 0;
        long long m = abs((long long)dividend), n = abs((long long)divisor);
        if (m < n) return 0;
        long long t = n, p = 1;
        while (m > (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p + divide(m - t, n);
        if ((dividend < 0) ^ (divisor < 0)) res = -res;
        return res > INT_MAX ? INT_MAX : res;
    }

https://leetcode.com/problems/divide-two-integers/discuss/13422/Accepted-Java-solution-with-comments.

public int divide(int dividend, int divisor) {
 long result = divideLong(dividend, divisor);
 return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
}

// It's easy to handle edge cases when
// operate with long numbers rather than int
public long divideLong(long dividend, long divisor) {
 
 // Remember the sign
 boolean negative = dividend < 0 != divisor < 0;
 
 // Make dividend and divisor unsign
 if (dividend < 0) dividend = -dividend;
 if (divisor < 0) divisor = -divisor;
 
 // Return if nothing to divide
 if (dividend < divisor) return 0;
 
 // Sum divisor 2, 4, 8, 16, 32 .... times
    long sum = divisor;
    long divide = 1;
    while ((sum+sum) <= dividend) {
     sum += sum;
     divide += divide;
    }
    
    // Make a recursive call for (devided-sum) and add it to the result
    return negative ? -(divide + divideLong((dividend-sum), divisor)) :
     (divide + divideLong((dividend-sum), divisor));
}

非死不可10/12面经
1. 不用 / 和 % 操作符做integer division。给出n和d, 求n / d和n % d。当时想了2个思路，一个O(n/d)的暴力破解，一个O(log(n))的binary search。都写出代码了，面试官让分析一下哪个快，假设n完全随机且d在[1, n]之间随机

对就是那题，但是简单了很多，0 < d <= n，少了很多烦人的case
然后可以用乘法？原题好像不允许用乘法，用乘法的话就直接二分法吧？

请问下O(n/d)和O(log(n))在d随机状态下怎么比较呢？是需要求O(n/d)的期望=1+1/2+1/3+..+1/n这样吗

是的，假设d在[1, n] 之间随机分布，求期望值。不过面试的时候只是很潦草的说了一下，并没有详细解释

余数可以算完商之后，用被除数减一下商*除数这样算么...

LeetCode 29 - Divide Two Integers

Labels

Popular Posts