Problem

At Stripe, you need to implement integer division for a low-level utility where the / and * operators are not allowed. Given two integers dividend and divisor, return the quotient after dividing dividend by divisor.

Truncate toward zero, as in most programming languages. You may not use multiplication, division, or modulus operators.

Formal Specification

• Input: Two integers, dividend and divisor
• Output: An integer quotient equal to dividend / divisor, truncated toward zero
• If the result overflows 32-bit signed integer range, return 2147483647

Examples

Example 1

• Input: dividend = 10, divisor = 3
• Output: 3
• Explanation: 10 / 3 = 3.333..., so truncating toward zero gives 3.

Example 2

• Input: dividend = 7, divisor = -3
• Output: -2
• Explanation: 7 / -3 = -2.333..., so truncating toward zero gives -2.

Constraints

• -2^31 <= dividend <= 2^31 - 1
• -2^31 <= divisor <= 2^31 - 1
• divisor != 0
• Your solution should run in O(log |dividend|) time or better