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://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 = 315 - 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:
  1. divisor = 0;
  2. 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] 之间随机分布,求期望值。不过面试的时候只是很潦草的说了一下,并没有详细解释
余数可以算完商之后, 用被除数减一下商*除数这样算么...

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts