[leetcode 29] Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note:

• Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^(31),  2^(31) − 1]. For this problem, assume that your function returns 2^(31) − 1 when the division result overflows.

 

Example 1:

Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = truncate(-2.33333..) = -2.

Example 3:

Input: dividend = 0, divisor = 1 Output: 0

Example 4:

Input: dividend = 1, divisor = 1 Output: 1

 

정수 나누기

양수 / 양수 = 양수

양수 / 음수 = 음수

음수 / 양수 = 음수

음수 / 음수 = 양수

 

둘 중에 하나라도 음수면 몫은 음수이다.

 

-2147483648 = INT_MIN, 2147483647 = INT_MAX

32비트 정수의 제한 조건이 [INT_MIN, INT_MAX]이고 오버플로우 발생시 INT_MAX을 리턴하도록 되어 있다.

 

나눠지는 수가 INT_MIN일 경우 -1로 나누면 오버플로우가 발생한다. 따라서 INT_MAX를 리턴한다.

 

나눠지는 수가 INT_MIN일 경우 절대값을 취하면 오버플로우가 발생하기 때문에 1을 더해서 -21....7을 만든다.

마지막에 오버플로우 때문에 +1을 더했다면 다시 원래 값으로 돌려주기 위해 절댓값에 +1을 해준다.

class Solution {
    public int divide(int dividend, int divisor) {
        
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        
        if(divisor == 1) return dividend;
        if(divisor == -1) return -dividend;
        
        if(divisor == Integer.MIN_VALUE) return dividend==Integer.MIN_VALUE ? 1:0;
        
        boolean negFlag = (dividend > 0) ^ (divisor > 0);
        
        boolean outOfRange = false;
        if(dividend == Integer.MIN_VALUE){
            dividend += 1;
            outOfRange = true;
        }
        
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        
        int quotient = 0;
        while(dividend >= divisor){
         
            quotient++;   
            dividend -= divisor;
        }
        
        if(outOfRange && (dividend+1)==divisor){
            quotient++;
        }
        
        return negFlag==false? quotient:-quotient;
    }
}