LeetCode - Algorithms - 29. Divide Two Integers

LeetCode – Divide Two Integers (Java) is the right answer, tested.

This problem can be solved based on the fact that any number can be converted to the format of the following, Power series of 2:

num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int divide(int dividend, int divisor) {
		if (divisor == 0)
			return Integer.MAX_VALUE;
		if (divisor == -1 && dividend == Integer.MIN_VALUE)
			return Integer.MAX_VALUE;

    	boolean sign = ((new Long(dividend)>0) && (new Long(divisor)>0)) || ((new Long(dividend)<0) && (new Long(divisor)<0)) ? true : false;

    	long dividend_abs = Math.abs(new Long(dividend));
    	long divisor_abs = Math.abs(new Long(divisor));

    	long quotient = 0;
		while (dividend_abs >= divisor_abs) {
			// calculate number of left shifts
			int numShift = 0;
			while (dividend_abs >= (divisor_abs << numShift)) {
				numShift++;
			}
			// dividend minus the largest shifted divisor
			quotient += 1 << (numShift - 1);
			dividend_abs -= (divisor_abs << (numShift - 1));
		}

    	return sign?new Long(quotient).intValue():-new Long(quotient).intValue();       
    }
}

Submission Detail

  • 989 / 989 test cases passed.
  • Runtime: 31 ms
  • Your runtime beats 30.12 % of java submissions.