Divide Two Integers Problem Solution

Divide Two Integers Problem: Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Example :

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Divide Two Integers Problem Solution

Problem Solution In Python

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend*divisor>0:
            res=abs(dividend)//abs(divisor)
        else:
            res=-(abs(dividend)//abs(divisor))
        intmin=-(2**31)
        intmax=(2**31)-1
        return res if intmin<=res<=intmax else intmax

Problem Solution In Java

public int divide(int dividend, int divisor) {
    boolean sign = true;
    long dividendL = dividend;
    long divisorL = divisor;
    if (dividendL < 0) {
        sign = !sign;
        dividendL = -dividendL;
    }
    if (divisorL < 0) {
        sign = !sign;
        divisorL = -divisorL;
    }
    List<long[]> memo = new ArrayList<>(); // the size of the list is at most 32. So it is O(1) space.
    long sum = divisorL;
    long mult = 1;
    memo.add(new long[]{sum, mult});
    while ( sum + sum <= dividendL ) {
        sum += sum;
        mult += mult;
        long[] current = {sum, mult};
        memo.add(current);
    }
    long res = 0;
    for (int i = memo.size() - 1; i >= 0; i--) {
        if (dividendL - memo.get(i)[0] >= 0) {
            dividendL -= memo.get(i)[0];
            res += memo.get(i)[1];
        }
    }
    if (!sign) res = -res;
    if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    else return (int) res;
}

Problem Solution In C++

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool negative = (dividend > 0) ^ (divisor > 0);
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;
        if(dividend > 0) dividend = -dividend;
        if(divisor > 0) divisor = -divisor; 
        int mul = divideHelper(dividend, divisor);
        return negative ? mul : -mul;
    }
    
private:
    int divideHelper(int dividend, int divisor) {
        if(dividend > divisor) return 0;
        int mul = -1;
        int sum = divisor;
        while(sum >= dividend - sum) {
            mul += mul;
            sum += sum;
            if(sum > 0) break;
        }
        return mul + divideHelper(dividend-sum, divisor);
    }
};

Problem Solution In C

int divide(int dividend, int divisor){
    int is_negative = (dividend > 0) ^ (divisor > 0);
    long long ll_dividend = dividend;
    long long ll_divisor = divisor;
    long long quotient = 1;
        
    ll_dividend = llabs(ll_dividend);
    ll_divisor = llabs(ll_divisor);

    long long sum = ll_divisor;

    while (sum < ll_dividend) {
        sum <<= 1;
        quotient <<= 1;
    }
    
    while (sum > ll_dividend)
    {
        sum -= ll_divisor;
        quotient--;
    }
    
    if (is_negative) {
        quotient = -quotient;
    }

    if (quotient < INT_MIN || quotient > INT_MAX)
    {
        return INT_MAX;
    }
    
    return quotient;
}