Integer Division without Operators

# Integer Division without Operators ## Difficulty Medium ## Tags `bit manipulation`, `math` ## Problem Statement Create a function that takes two integers, `dividend` and `divisor`, and returns their quotient. The function should mimic the behavior of the integer division operator `/` but must **not** use the division (`/`), multiplication (`*`), or modulo (`%`) operators. ## Constraints - The input integers are 32-bit signed integers. - The environment can only store integers within the 32-bit signed integer range: [-2³¹, 2³¹ - 1]. - If the quotient is strictly greater than 2³¹ - 1, return 2³¹ - 1. - If the quotient is strictly less than -2³¹, return -2³¹. - Division by zero should return 2³¹ - 1 (or raise an exception). ## Signatures ### Python ```python def divide(dividend: int, divisor: int) -> int: pass ``` ### Java ```java public class Solution { public int divide(int dividend, int divisor) { return null; } } ``` ### Csharp ```csharp public class Solution { public int divide(int dividend, int divisor) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int divide(int dividend, int divisor) { } }; ``` ### C ```c int divide(int dividend, int divisor) { } ``` ### Ruby ```ruby def divide(dividend, divisor) end ``` ### Perl ```perl sub divide { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def divide(dividend: Int, divisor: Int): Int = { } } ``` ### Haskell ```haskell divide :: ... -> ... divide args = undefined ``` ### Clojure ```clojure (defn divide [dividend divisor] ) ``` ### Scheme ```scheme (define (divide dividend divisor) ) ``` ## Examples ### Example 1 **Input:** ``` dividend = 10 divisor = 3 ``` **Output:** ``` 3 ``` **Explanation:** 10 divided by 3 is 3.333..., which truncates to 3. ### Example 2 **Input:** ``` dividend = 7 divisor = -3 ``` **Output:** ``` -2 ``` **Explanation:** The result truncates towards zero. ### Example 3 **Input:** ``` dividend = -2147483648 divisor = -1 ``` **Output:** ``` 2147483647 ``` **Explanation:** Overflow case - result would be 2³¹, which exceeds the max, so return 2³¹ - 1. ## Hints 1. Division is essentially repeated subtraction. 2. Think about binary representation - can you subtract multiples of the divisor (shifted by powers of 2)? 3. This approach achieves O(log N) time complexity.