Question Link

https://leetcode.com/problems/divide-two-integers/

Question Description

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

Simulation

Solution 1: Brutal - Minus

Input: Divident = 7, Divisor = -3
This approach is based on the idea the division is simply multiple minues. Then, we will need to handle the edge case of minues number.

Solution 2: Bit + Greedy

Input: Divident = 10, Divisor = 3

Implementation

Solution 1: Brutal - Minus

Below solution doesn’t handle any edge case of overflow…

public int divide(int dividend, int divisor) {
    if (divisor == 1) {
        return dividend;
    }
    boolean isPositive = false;
    int count = 0;
    if ((dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0))
        isPositive = true;
    if (dividend < 0)
        dividend *= -1;
    if (divisor < 0)
        divisor *= -1;
    while (dividend >= divisor) {
        dividend -= divisor;
        count++;
        if (count == Integer.MAX_VALUE) {
            break;
        }
    }
    return isPositive ? count : count * -1;
}

Solution 2: Bit + Greedy

public int divide(int dividend, int divisor) {
    boolean isNegative = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ? true : false;
    long absDividend = Math.abs((long) dividend);
    long absDivisor = Math.abs((long) divisor);
    long result = 0;
    while(absDividend >= absDivisor){
        long tmp = absDivisor, count = 1;
        while(tmp <= absDividend){
            tmp <<= 1;
            count <<= 1;
        }
        result += count >> 1;
        absDividend -= tmp >> 1;
    }
    return  isNegative ? (int) ~result + 1 : result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result;
}