Algorithm-Day29-Divide-Two-Integers-lc-29

---

🧩 Problem Description

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

Return the quotient after dividing dividend by divisor.

The result should be truncated toward zero (i.e., 8.9 → 8, -8.9 → -8).

---

💬 Example

Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

---

⚠️ Constraints

• You must not use *, /, or %.
• Range of inputs: -2³¹ ≤ dividend, divisor ≤ 2³¹ - 1
• If result overflows (> 2³¹ - 1), return 2³¹ - 1

---

💡 Intuition

To simulate division:

• Keep subtracting the divisor from dividend until the dividend is smaller than divisor.
• To speed up, use bit shifting (double the divisor each time).

This is like long division: find the largest multiple of divisor that fits in dividend.

---

🔢 Java Code (Bit Manipulation)

class Solution {
    public int divide(int dividend, int divisor) {
        // Edge case: overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        // Use long to prevent overflow during shifting
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int result = 0;

        while (a >= b) {
            long temp = b;
            int multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            result += multiple;
        }

        // Determine sign
        return (dividend > 0) == (divisor > 0) ? result : -result;
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(log N) — where N is |dividend|
• Space Complexity: O(1)

---

✍️ Summary

• No multiplication, division, or modulus — use bit shifts and subtraction.
• Carefully handle:
  • Negative numbers
  • Edge cases like Integer.MIN_VALUE / -1
• This is a good exercise in low-level arithmetic logic.

Learn this if you want to understand how division could be implemented in systems without direct hardware division support.