2014年4月11日 星期五

[LeetCode] Divide Two Integers

Problem:
Divide two integers without using multiplication, division and mod operator.
Solution O(log n)


public class Solution {  
    public int divide(int dividend, int divisor) {  
        int sign = 1;  
        if(dividend < 0){  
            sign *= -1;  
        }  
        if(divisor < 0){  
            sign *= -1;  
        }  
        long a = Math.abs((long)dividend);  
        long b = Math.abs((long)divisor);  
        int count = 0;  
        while(a >= b){  
            long temp = b;  
            int mul = 1;  
            while(a >= temp){  
                count += mul;  
                a -= temp;  
                temp += temp;  
                mul += mul;  
            }  
        }  
        return count * sign;  
    }  
}
Key concept: Use long to avoid Integer overflow and use binary decode to get the answer

沒有留言:

張貼留言