A readable Java implementation


  • 14
    B

    At first, I used dividend / divisor, just to check. But that was cheating.

    Then, I implemented a solution which failed the corner cases. I solved it by using long instead of int. But I felt that was also cheating.

    At last, I came up with this solution. It handles all the corner cases. Running time analysis after the code.

    public class Solution {
        public int divide(int dividend, int divisor) {
            if (divisor == 1) // Trival case 1
                return dividend;
            
            // Use negative integers to avoid integer overflow
            if (dividend > 0)
                return -divide(-dividend, divisor);
            if (divisor > 0)
                return -divide(dividend, -divisor);
            
            if (dividend > divisor) // Trivial case 2
                return 0;
            
            if ((dividend == Integer.MIN_VALUE) && (divisor == -1)) // Overflow case
                return Integer.MAX_VALUE;
            
            // Find the highest mult = (divisor * 2^shifts) which is <= dividend
            // by shifting mult to the left without causing an overflow.
            // At most (log2(|dividend|) - log2(|divisor|) + 1) iterations.
            int min_divisor = Integer.MIN_VALUE >> 1;
            int mult = divisor; // = divisor * 2^shifts
            int shifts = 0;
            while ((mult >= min_divisor) && (mult > dividend)) {
                mult <<= 1;
                ++shifts;
            }
            
            // Compute the result by shifting mult to the right.
            // At most (log2(|dividend|) - log2(|divisor|) + 1) iterations for the outer loop.
            // At most (log2(|dividend|) - log2(|divisor|) + 1) iterations for the inner loop
            // (in total, not per outer iteration).
            int result = 0;
            int power = 1 << shifts; // = 2^shifts
            while (dividend <= divisor) {
                shifts = 0;
                while (mult < dividend) {
                    mult >>= 1;
                    ++shifts;
                }
                dividend -= mult;
                power >>= shifts;
                result |= power; // Adds power to result
            }
            
            return result;
        }
    }
    

    I see lots of people talking about O(log(n)) solutions. Since n is bounded by -2^31 and 2^31-1, I'm not sure the Big-Oh notation is appropriate here. Anyway, here's a rough worst-case analysis of this code.

    The first loop runs (log2(|dividend|) - log2(|divisor|) + 1) times. There are

    • 2 comparisons
    • 1 bit shift
    • 1 increment

    The second loop runs between 1 time and (log2(|dividend|) - log2(|divisor|) + 1) times. For worst-case, we take the latter. There are

    • 1 comparison
    • 1 assignment
    • 1 substraction
    • 1 bit shift
    • 1 bitwise or

    The inner while loop runs (log2(|dividend|) - log2(|divisor|) + 1) times also (in total, not per outer loop iteration). There are

    • 1 comparison
    • 1 bit shift
    • 1 increment

    So, roughly, the overall worst-case running time is 12(log2(dividend) - log2(divisor) + 1) operations. You can notice that (log2(|dividend|) - log2(|divisor|)) = log2(|result|). Thus, the running time is (worst-case) 12(log2(|result|) + 1) operations.


  • 0
    S

    I don't understand the meaning of this line: if (dividend > divisor) // Trivial case 2
    return 0;
    When I deleted it, the code was still AC.
    But I really don't see how is this trivial case (i.e. Dividend = 5, divisor = 2) (5>2) -> 0? Why? It should return 2. Nevertheless, as I said the code never pass through these two lines, so I deleted them.


  • 1
    B

    dividend and divisor are both negative. So, you'd get to this line by calling divide(2, 5) because -2 > -5.

    Now, this line is not "necessary" because the code will "compute" the right result. But if you get to this line and the condition is verified, you can return the result without computing it at all, which is better.


  • 0
    S

    I see, thanks!


  • 0
    B

    You're welcome.


  • 1
    S

    This part make me think you're a clever person.

    // Use negative integers to avoid integer overflow
    if (dividend > 0)
    return -divide(-dividend, divisor);
    if (divisor > 0)
    return -divide(dividend, -divisor);


  • 0
    H

    I think it's better to use "if (divisor == -1)" for trivial case 1, since you are using negative integers.


  • 0
    B

    It would work for anything except divide(-2147483648, 1). So, to handle this corner case, you have to use if (divisor == 1).


  • 0
    H

    It makes sense. By the way, how do you handle the 988-th test case: "(-2147483648, -1), Expected: 2147483647"?


  • 0
    B

    I don't do anything special. It's not a trivial case so, it must be handled by the main algorithm.


  • 8
    L

    Mine:

    public class Solution {
        public int divide(int dividend, int divisor)
        {
            if (divisor == 0)
            {
                return Integer.MAX_VALUE;
            }
            else if (divisor == 1)
            {
                return dividend;
            }
            else if (divisor == -1)
            {
                return (dividend == Integer.MIN_VALUE) ? Integer.MAX_VALUE : -dividend;
            }
            else
            {
                final boolean negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
                
                long ldividend = Math.abs((long) dividend);
                final long ldivisor = Math.abs((long) divisor);
                int result = 0;
                
                for (int bit = Integer.SIZE - 1; bit >= 0 && ldividend >= ldivisor; --bit)
                {
                    if (ldividend >= (ldivisor << bit))
                    {
                        ldividend -= ldivisor << bit;
                        result |= 1 << bit;
                    }
                }
                
                return negative ? -result : result;
            }
        }
    }

  • 0
    N
    This post is deleted!

  • 0
    N

    Ihave a litter confused about " result |= 1 << bit;".
    why not result = result + 1<< bit;?
    Sorry, I understand , In this case ,it's the same.


  • 0
    S

    Hi, this code cannot deal with -2147483648 / -1. It's outputing -2147483648


  • 0
    B

    You're right. The overflow case was added after I submitted my code. I added this test after the trivial case 2 to handle it

        if ((dividend == Integer.MIN_VALUE) && (divisor == -1)) // Overflow case
            return Integer.MAX_VALUE;
    

  • 0
    S

    Never Mind. Great code though, you are the only one who use negative value to deal with overflow.


  • 0
    A

    coz result +1 can coz carry out to next bit?


  • 0

    I am a little confused by this part:

        int min_divisor = Integer.MIN_VALUE >> 1;
    

    What does the min_divisor mean? I think it is a fixed negative number. Why you use it as a negative number?


  • 0
    B

    This is to prevent overflow by left-shifting too much.


  • 0

    And how about the first while loop? The mult was initilized by divisor, and the previous if limited that divisor must smaller than dividend. I found the first loop will not work at all, because the second while condition is always false.

        while ((mult >= min_divisor) && (mult > dividend)) 
    

    Am I right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.