Divide Two Integers

Question: 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.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

You may view the full question here.

Approach 1: As usual, let’s start with something straight forward and naive. Multiplication is repeated addition. From this we can arrive at the following code —

//Approach 1:
//RunTime: Time Limit Exceeded
//Memory usage: N/A

class Solution {
    public int divide(int dividendI, int divisorI) {
        int sign = 1;
        int signD = 1;
        double dividend = dividendI;
        double divisor = divisorI;
        if(divisor<0){
            sign = -1;
            divisor*=-1;
        }
        if(dividend<0){
            signD = -1;
            dividend*=-1;
        }
        int q = 0;
        if(divisor==1){
            double result = dividend*sign*signD;
            if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE){
                return Integer.MAX_VALUE;
            }

            return (int)result;
        }
        while(dividend>=divisor){
            dividend-=divisor;
            q++;
        }
        return q*sign*signD;
    }
}

Clearly, we have a long way to go.

Approach 2: After a few hours of toil, we got better . Back at school, remember the way we did long division. The following code, does exactly that for us —

//Approach 2:
//Runtime: 1ms
//Memory usage: 32.5MB

class Solution {
    public int divide(int dividend, int divisorI) {
        int signDs = getSign(divisorI);
        int signDd = getSign(dividend);
        double divisor = (double)divisorI * signDs;

        double q = 0;
        double rem = 0;
        char[] chars = String.valueOf(dividend).toCharArray();
        for(char c : chars){
            if(c=='-'){
                continue;
            }
            rem = rem * 10 + (c - '0');
            int tempQ = 0;
            while(rem>=divisor){
                tempQ++;
                rem-=divisor;
            }
            q=q*10 + tempQ;
        }
        if(q*signDs*signDd > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        return (int)(q*signDs*signDd);
    }

    private int getSign(int num){
        if(num<0){
            return -1;
        }
        return 1;
    }
}

Find more posts here.

Cheers & Chao!