224. Divide Two Integers Without Using *, /, or %

Given two integers, dividend and divisor, compute their integer quotient (truncated toward zero, the way most languages' integer division works) without using the *, /, or % operators.

Input: Two lines: the first contains dividend, the second contains divisor. Output: Print a single integer - the quotient truncated toward zero.

-2*10^9 <= dividend, divisor <= 2*10^9, divisor != 0

Watch for the classic overflow edge case: dividing the most negative possible integer by -1 can overflow the maximum positive integer representable - real solutions to this exact LeetCode-style problem explicitly guard against that edge case.

You need to figure out how many times one number fits into another (division), but you can't use the divide, multiply, or remainder operators at all - only addition, subtraction, and bit shifts. Brute force: Repeatedly subtract the divisor from the dividend one single copy at a time, counting how many subtractions succeed before the remainder drops below the divisor - correct, but for a dividend near 2 billion and a divisor of 1, this could take up to 2 billion subtraction steps, which is far too slow. Optimised: Instead of subtracting the divisor one copy at a time, subtract the LARGEST possible power-of-2 multiple of it that still fits - this is exactly how binary long division works, and it reduces the number of steps from 'proportional to the dividend's VALUE' down to 'proportional to the number of BITS in the dividend' (roughly 30-60 steps at most).

Instead of subtracting the divisor one copy at a time, subtract as many copies as possible at once: for the current remaining dividend, find the largest value divisor << k (divisor doubled k times using a left shift, not multiplication) that still fits, subtract it, and add 2^k to the quotient. Repeat this 'doubling subtraction' until the remainder is smaller than the divisor. Each round eliminates roughly half the remaining magnitude, so the number of rounds and the per-round search are both logarithmic in the dividend, a massive improvement over subtracting one divisor at a time. Time: O(log^2(dividend)) Space: O(1)

Determine the sign of the result from the signs of dividend and divisor, then work with their absolute values. Repeatedly subtract the divisor from the (absolute) dividend, incrementing a counter each time, until what remains is smaller than the divisor; the counter is the quotient. This directly mirrors what division means (how many times does the divisor fit into the dividend), but if the quotient is large (e.g. dividing 2*10^9 by 1) this takes billions of subtractions and is far too slow. Time: O(quotient) Space: O(1)

Treat this like binary long division: scan bit positions of the quotient from the highest possible (around bit 31 down to 0) once, maintaining a shifted remainder. At each bit position, check if (divisor << bit) fits within the remaining dividend; if it does, subtract it and set that bit of the quotient. Because each bit is decided exactly once in a single top-down pass (no repeated searching from scratch like in the doubling approach), this achieves the same doubling trick but in a single linear scan over the bits, which is asymptotically optimal since you must at least inspect O(log(dividend)) bits. Care is taken with signs and the INT_MIN edge case by working in a wider integer type. Time: O(log(dividend)) Space: O(1)

1. Work with the absolute values of both numbers, and separately track whether the final answer should be negative (exactly one of dividend/divisor being negative). 2. Try to subtract the LARGEST possible shifted multiple of the divisor (divisor doubled repeatedly: divisor, divisor*2, divisor*4, ...) from the remaining dividend. 3. Each time you successfully subtract a shifted multiple, add the corresponding power of 2 to your running quotient count. 4. Repeat with whatever remains until the divisor (even un-shifted) no longer fits - the accumulated quotient count is your answer, with the correct sign reapplied.

Time: Proportional to the number of bits in the dividend (around 30-60 steps) - essentially instant regardless of how large the actual numbers are. Space: O(1) - just a few running variables for the quotient, remainder, and sign.

Test negative dividend and/or divisor (sign of the result must be handled), divisor = 1, and magnitudes near the extremes (-2*10^9 to 2*10^9) to confirm no overflow during doubling.

Be ready to explain why naive repeated single-step subtraction is too slow, and why doubling the divisor at each step (binary long division) fixes it - this specific 'why' is what separates a working brute force from the expected optimized answer here.