29. Divide Two Integers

Time: O(log^2 n)

Space: O(1)

Intuition

Division without multiplication/division: use bit-shifting to implement exponential doubling. Find the largest multiple of divisor (as a power of 2) that fits in dividend, subtract it, record the multiple, and repeat. This achieves O(log^2 n) instead of O(n) for repeated subtraction.

Algorithm

1Handle overflow: if dividend == INT_MIN and divisor == -1, return INT_MAX.
2Track sign: result is negative if exactly one of dividend/divisor is negative. Work with absolute values.
3While |dividend| >= |divisor|: double divisor (shift left) and double count (1 << shift) until it overshoots. Back off one step. Subtract from dividend, add count to result.
4Repeat until dividend < divisor.
5Apply sign and return.

Example Walkthrough

Input: dividend = 10, divisor = 3

1.Both positive. |10| >= |3|: 3<<1=6 fits, 6<<1=12 > 10. Back off: subtract 6, result=2. Remaining=4.
2.|4| >= |3|: 3<<1=6 > 4. Subtract 3, result=3. Remaining=1.
3.|1| < |3|. Done. result=3.

Output: 3

Common Pitfalls

•Must handle INT_MIN / -1 = INT_MAX overflow separately.
•Use long arithmetic for intermediate values to avoid overflow during doubling.

29.cs

// Approach: Repeated doubling (bit-shift) to avoid the division operator.
// For each step, find the largest multiple of divisor (= divisor << k) that fits in the remaining dividend.
// Subtract it, add 2^k to the quotient, and repeat with the remainder.
// Use long to handle INT_MIN / -1 overflow and sign separately.
// The outer loop runs O(log n) times; inner doubling also runs O(log n) — total O(log^2 n).
// Handle edge cases: INT_MIN / -1 = INT_MAX (clamp), INT_MIN / 1 = INT_MIN.
// Time: O(log^2 n) Space: O(1)

public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        if (divisor == 1)
            return dividend;

        if (dividend == int.MinValue && divisor == -1)
            return int.MaxValue;

        bool sign = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        int ans = 0;
        while (dividend <= divisor)
        {
            int x = divisor;
            int cnt = 1;
            while (x >= (int.MinValue >> 1) && dividend <= (x << 1))
            {
                x <<= 1;
                cnt <<= 1;
            }
            ans += cnt;
            dividend -= x;
        }
        return sign ? ans : -ans;
    }
}

Was this solution helpful?