LeetCode Problem Link

Naive Appraoch -

Intuition-

• Initialize a sum variable to track the current total.

• Initialize a count variable to count the number of times the divisor can be added to the sum without exceeding the dividend.

• Iterate until the sum of the divisor exceeds the dividend:

  • Increment the count.

  • Add the divisor to the sum.

• Return the count as the quotient if the sign flag is true.

• Otherwise, return the negation of the count as the quotient.

// Java Code
class Solution {
    public int divide(int dividend, int divisor) {
        int sum = 0;
        int cnt = 0;
        boolean sign = true;
        if(dividend >= 0 && divisor < 0) sign = false;
        if(dividend <= 0 && divisor > 0) sign = false;
        divisor = Math.abs(divisor);
        while(sum + divisor <= dividend){
            cnt++;
            sum += divisor;
        }
        return sign ? cnt : -cnt;
    }
}

// C++ Code
int divide(int dividend, int divisor) {
    int sum = 0;
    int cnt = 0;
    bool sign = true;
    if ((dividend >= 0 && divisor < 0) || (dividend <= 0 && divisor > 0)) sign = false;
    divisor = abs(divisor);
    while (sum + divisor <= dividend) {
        cnt++;
        sum += divisor;
    }
    return sign ? cnt : -cnt;
}

# Python Code
def divide(dividend: int, divisor: int) -> int:
    sum_val = 0
    cnt = 0
    sign = True
    if (dividend >= 0 and divisor < 0) or (dividend <= 0 and divisor > 0):
        sign = False
    divisor = abs(divisor)
    while sum_val + divisor <= dividend:
        cnt += 1
        sum_val += divisor
    return cnt if sign else -cnt

---

Optimal Approach - Bit Manipulation

Intuition -

    dividend = (quotient) * divisor + remainder

We have to find the quotient in this equation and we are given divisor and dividend.
Any number can be represented in binary form. Same goes for quotient :

Let us have an example: 58/5:
58 = (11) * 5 + 3
Representing the quotient in binary form: (11)₁₀ = (1011)₂:

    58 = (2^3 + 2^1 + 2^0) * 5 + 3                // --- (I)
    58 = [(2^3 * 5) + (2^1 * 5) + (2^0 * 5)] + 3  // --- (II)

Since we dont know the quotient and remainder the equation we know is:
58 = (q) * 5 + rem

We get a hint at what we would like to do here. We will first multiply 5 with maximum power of 2 such that the resulting number is still smaller than the dividend (read further if you don't understand why). Since multiplication operator is not allowed, we would use bitwise left shift to achieve this multiplication: each time we shift 5 by 1, we multiply it by 2:

    5 << 0 = 5               // less than dividend
    5 << 1 = 5*2 = 10        // less than dividend
    5 << 2 = 5*2*2 = 20      // less than dividend
    5 << 3 = 5*2*2*2 = 40    // less than dividend
    5 << 4 = 5*2*2*2*2 = 80  // (stop and consider the previous value as the result is greater than dividend

We observe that:
58 = (2^3 * 5) + (something * 5) + rem // --- (III)
You can see we are getting close to the equation we initialy wanted (eqa II).

Since 5 is multiplied with 2³, we add 2³ to our answer.
Further operating on equation III:

    58 - (2^3 * 5)  =  (something * 5) + rem
    58 - (8 * 5) = something * 5 + rem
    58 - 40 = something * 5 + rem
    18 = something * 5 + rem

What we effectively have done is, subtracted the result we got from our first step from dividend (58 - 40).
We arived at the same question again but with a smaller dividend this time.
dividend = 18, divisor = 5

Therefore let us repeat the process:

    5 << 0 = 5           // less than dividend
    5 << 1 = 5*2 = 10    // less than dividend
    5 << 2 = 5*2*2 = 20  // (stop and consider the previous value as the result is greater than dividend

We add 2¹ to our answer.
Looking back:

    18  =  (2^1 * 5) + (something * 5) + rem
    58 - (2^3 * 5) = (2^1 * 5) + (something * 5) + rem
    58 =  (2^3 * 5) + (2^1 * 5) + (something * 5) + rem

You can notice we are gradually advancing towards equ II:
Our new dividend is now:

    18 - (2^1 * 5)  =  (something * 5) + rem
    18 - (2 * 5) = something * 5 + rem
    18 - 10 = something * 5 + rem
    8 = something * 5 + rem

dividend = 8, divisor = 5
Repeating the process:

    5 << 0 = 5           // less than dividend
    5 << 1 = 5*2 = 10    // (stop and consider the previous value as the result is greater than dividend

We add 2⁰ to our answer.
New dividend:

    8 = (2^0 * 5) + (something * 5) + rem
    8 - 5 = something * 5 + rem
    3 = something * 5 + rem

dividend = 3, divisor = 5
At this step, we stop iterating as our dividend is less than the divisor (we have also found our remainder = 3, as 5 should be multiplied with 0 and what remains is the remainder).

Looking back again for the last time:

    3 = 0*5 + rem
    8 = (2^0 * 5) + 3
    18  =  (2^0 * 5) + (2^1 * 5) + 3
    58 = (2^3 * 5) + (2^1 * 5) + (2^0 * 5) + 3

In the process, we have finally reached the equation we wanted to, and have got the answer as:
quotient = (2^3 + 2^1 + 2^0)

---

// Java Code
class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == divisor) return 1;
        boolean sign = true;
        if(dividend >= 0 && divisor < 0) sign = false;
        if(dividend <= 0 && divisor > 0) sign = false;

        long n = Math.abs((long)dividend);
        long d = Math.abs((long)divisor);
        divisor = Math.abs(divisor);
        long quotient = 0;
        while( n >= d){
            int cnt = 0;
            while(n >= (d << (cnt+1))) cnt++;
            quotient += 1 << cnt;
            n -= (d << cnt);
        }
        if(quotient == (1 << 31) && sign) return Integer.MAX_VALUE;
        if(quotient == (1 << 31) && !sign) return Integer.MIN_VALUE;

        return sign ? (int)quotient : -(int)quotient;
    }
}

// C++ Code 
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == divisor) return 1;
        bool sign = true;
        if (dividend >= 0 && divisor < 0) sign = false;
        if (dividend <= 0 && divisor > 0) sign = false;

        long long n = abs(dividend);
        long long d = abs(divisor);
        divisor = abs(divisor);
        long long quotient = 0;

        while (n >= d) {
            int cnt = 0;
            while (n >= (d << (cnt + 1))) {
                cnt++;
            }
            quotient += 1 << cnt;
            n -= (d << cnt);
        }

        if (quotient == (1LL << 31) && sign) return INT_MAX;
        if (quotient == (1LL << 31) && !sign) return INT_MIN;

        return sign ? quotient : quotient;
    }
};

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == divisor:
            return 1
        sign = True
        if dividend >= 0 and divisor < 0:
            sign = False
        if dividend <= 0 and divisor > 0:
            sign = False

        n = abs(dividend)
        d = abs(divisor)
        divisor = abs(divisor)
        quotient = 0

        while n >= d:
            cnt = 0
            while n >= (d << (cnt + 1)):
                cnt += 1
            quotient += 1 << cnt
            n -= (d << cnt)

        if quotient == (1 << 31) and sign:
            return 2147483647
        if quotient == (1 << 31) and not sign:
            return -2147483648

        return quotient if sign else -quotient

---

That's it !
Thanks for the reading the entire blog.

Connect me on X - @DexterIfti