[LeetCode] Divide Two Integers (Java)

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

Analysis

We can keep subtract divisor from dividend until dividend is smaller than 0, than count the subtract numbers. But it will costs a very long time if the divisor is very small comparing to dividend.

Shift can be used to solve this problem. We shift the divisor left until it just smaller than dividend but if we keep shifting one more bit, it’s larger than dividend. Than we can add the shifted value to the result and subtract the shifted value from dividend. Keep doing this until dividend is smaller than divisor. In fact, every integer can be represented by a set of base 2 so that shifting can be used.

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.

Code

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

 Complexity

The complexity is O(log n).

  • Hi, I think you ignored the case of ret = 2147483648. In this case, you should return 2147483647 but not 2147483648.

    • decoet

      Yes! They add that case after I write the code. This should be the bug in my code, and I will update it some time. Thank you.

  • your code can’t pass all the test on leetcode

    • decoet

      Yes. Actually leetcode update their test cases after some time I wrote this code. But I am quite lazy to update it. 🙂

  • Sam Xie

    good solutions.

  • mentalist

    Not able to understand the logic behind the code. Why shifting by (counter – 1) why not counter? How will this approach ensure the right answer?
    while(p >= q) {
    int counter = 0;
    while (p >= (q << counter)) {
    counter++;
    }
    ret += 1 << (counter – 1);
    p -= q << (counter – 1);
    }
    Code is well written, please explain the logic behind it. Thank you

    • decoet

      You can test it with a test case. In this loop:
      while (p >= (q < < counter)) { counter++; } You will find that when condition holds, counter is not big enough. In this loop we are going to find the max counter that make p >= (q << counter). When the condition doesn't hold, the counter is larger than what we want. So we need to minus 1 to get the value we need.