Clean Java solution with some comment.


  • 58
    J
    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);
    }

  • 3
    M

    what is the run time of this algorithm?


  • 0
    J

    good idea, but still TLE


  • 0

    Nice explanation with good self-descriptive identifiers. This solution shows that every number can be represented as sum of powers of 2 which is somewhat similar to how binary search works .
    Also , no need to return Integer.MIN_VALUE since problem statement says return MAX_INT in case of overflow.


  • 0
    E

    In java, Integer.MAX_VALUE is a built-in static parameter representing 2^31-1. Problem asks you to return max integer value, describing in a programming language way of saying 'MAXINT', MAXINT is not a instance variable which has already been put in Solution Class so returning MAXINT will cause compile error.


  • 0

    By MAXINT , I meant value 2^31-1 in general.
    Yes , it will be Integer.MAX_VALUE in case of Java.


  • 11
    E

    Nice solution. Here is my shorter and easier to understand code.

    Hint:

    1. The divisor will never be 0.

    2. Make the divisor as big as possible.

    3. long to int, narrow down the range and then convert.

      public class Solution {
      public int divide(int dividend, int divisor) {
      if (dividend == 0) {
      return 0;
      }
      boolean neg = (dividend < 0) ^ (divisor < 0);
      long m = Math.abs((long)dividend), n = Math.abs((long)divisor);
      long result = 0;
      while (m >= n) {
      int shift = 0;
      while (m > (n << shift + 1)) {
      shift++;
      }
      m -= n << shift;
      result += (1 << shift);
      }
      result = (neg) ? ~(result - 1) : result;
      result = Math.min(Integer.MAX_VALUE, result);
      result = Math.max(Integer.MIN_VALUE, result);
      return (int)result;
      }
      }


  • 3
    M

    thanks for sharing! we are on the same track, yet i think my code is shorter and clearer:

    /*
        -- possible overflow: Integer.MIN_VALUE / (-1); anything / 0.
    */
    public class Solution {
        public int divide(int dividend, int divisor) {
            if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
            int sign = (dividend ^ divisor) >> 31;
            int quotient = divideHelper(Math.abs(Long.valueOf(dividend)), Math.abs(Long.valueOf(divisor)));
            return sign == 0 ? quotient : -quotient;
        }
        
        private int divideHelper(long top, long bot) {
            if (top < bot) return 0;
            long cur = bot;
            int count = 1;
            while (cur <= (top >>> 2)) {
                cur <<= 1;
                count <<= 1;
            }
            count += divideHelper(top - cur, bot);
            return count;
        }
    }
    

  • 2
    X

    in which context that result could overflow


  • 6

    Keep substracting divisor and double it each time. Whenever you overshoot and divisor goes more than dividend, go back to previous value, and try again.

    public int divide(int a, int b) {
        if(a==Integer.MIN_VALUE){
            if(b==-1) return Integer.MAX_VALUE;
        }
    
        long x = a < 0 ? -(long)a : (long)a;
        long y = b < 0 ? -(long)b : (long)b;
    
        int res = recurse(x, y, 1);
        if(a < 0 && b < 0) return res;
        if(a < 0 || b < 0) return -res;
        return res;
    }
    
    public int recurse(long x, long y, int count) {
        if(x <= 0 || count==0) return 0;
        if(y > x) return recurse(x, y >>> 1, count >>> 1); //overshot, so divide and try again.
        else return recurse(x-y, y+y, count+count)+count;
    }

  • 0
    J

    why result = (neg) ? ~(result - 1) : result;?
    I do not understand how it makes result to take the negative result value.


  • 0
    F
    This post is deleted!

  • 2
    Y

    @xia9 for example, Integer.MIN_VALUE / -1 will cause a overflow.


  • 0
    E

    public class Solution {
    public static int divide(int dividend, int divisor) {
    if(divisor==0||dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
    if(divisor==1) return dividend;
    int sign=((dividend>0)^(divisor>0))?-1:1;
    long did=Math.abs((long)dividend);
    long div=Math.abs((long)divisor);
    int res=0;
    while(did>=div){
    long tmp=div;
    int mutiple=1;
    while(did>=(tmp<<1)){
    tmp<<=1;
    mutiple<<=1;
    }
    did-=tmp;
    res+=mutiple;
    }
    return sign==-1?-res:res;
    }
    }


  • 0
    T

    your code is nicely structured and easy to understand! Thanks for your solution!


  • 0
    S

    anyone know why this method have to use "long" type
    I understand the other method by using bit operation.
    However, I don't think it is necessary to use long in this recursion method. Since inputs are valid. the "lans" should never be larger than dividend


  • 1
    Y

    @sixgod Suppose you use Math.abs() for Integer.MIN_VALUE. The absolute value of Integer.MIN_VALUE would overflow if not use long type.


  • 0

    @jaqenhgar Hello , I find out that in your solution when I change if(x <= 0 || count==0) return 0;
    into if(x == 0 || count==0) return 0;,it also works well and even faster. So is there any reason why you choose the first one?


  • 0
    Y

    Thank you @jinwu for your idea. I think your implementation can be simplified.
    Your idea is mainly based on long division.
    Here is the simplified implementation based on long division:

    public int divide(int dividend, int divisor) {
            if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
            // idea similar to "long division"
            int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;// XOR to determine same sign?
            long ldividend = Math.abs((long)dividend);
            long ldivisor = Math.abs((long)divisor);
            long multiple = 1;
            long ans = 0;
            // STEP 1: shift "divisor" to the most siginificant bit
            while ((ldivisor << 1) <= ldividend) {
                multiple <<= 1;
                ldivisor <<= 1;
            }
            // STEP 2: shift right to perform "long division"
            while (multiple > 0) {
                if (ldividend >= ldivisor) {
                    ldividend -= ldivisor;
                    ans += multiple;
                }
                multiple >>= 1;
                ldivisor >>= 1;
            }
            return sign == 1 ? (int)ans : (int)-ans;
        }
    

  • 0
    P
    This post is deleted!

Log in to reply
 

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