Leetcode Divide Two Integers problem solution

YASH PAL,

In this Leetcode Divide Two Integers problem solution we have 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.

Leetcode 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;
}

coding problems