29 Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

// complement + 1
// or just add (-) sign
int negate(int num) {
    return ~num + 1;
}

// slow method, unaccepted
int divide(int dividend, int divisor) {
    if (divisor == 0) return INT_MAX;
    if (divisor == 1) return dividend;

    bool neg_flag = (dividend < 0 ^ divisor < 0);
    dividend = abs(dividend);
    divisor = abs(divisor);

    int fits = 0;
    while (dividend >= 0) {
        if (dividend - divisor < 0) {
            if (neg_flag) return negate(fits);
            return fits;
        }

        else if (fits == INT_MAX) {
            if (neg_flag) return negate(fits);
            return fits;
        }

        else {
            dividend -= divisor;
            fits++;
        }
    }
}

Last updated