Given two integers `dividend`

and `divisor`

, divide them and output the quotient, without using multiplication, division and mode operator.

**Note:**

- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2
^{31}, 2^{31}− 1]. For the purpose of this problem, assume that your function**returns 2**.^{31}− 1 when the division result overflows

## Examples

Input: Dividend = 10, Divisor = 3 Output = 3 Explanation: 10/3 = 3.333. So the answer is 3

Input: Dividend = 1542, Divisor = 17 Output = 90 Explanation: 1542/17 = 90.70. So the answer is 90.

## Solution

Let us call the answer to the problem as `ans`

(which is the quotient when you divide dividend by divisor)

Since `ans`

is the quotient, following is true:

ans*divisor <= dividend.

Similarly, for any number `x`

greater than `ans`

, the following is true

x*divisor > dividend

And for any number `y`

less than `ans`

, the following is true

y*divisor < dividend

We can use the above properties to implement a solution using binary search.

If we remove the edge cases (we can handle them separately), we know that the quotient will be b/w `0`

and `dividend`

. Therefore, we can apply a binary search b/w `0`

and `dividend`

.

If the `mid*divisor > dividend`

, then make go left and make `hi = mid - 1`

, Otherwise save the mid and do `low = mid + 1`

.

## Solution Implementation

class Solution { public: int divide(int dividend, int divisor) { unsigned long long int lo = 0; unsigned long long int hi = abs(dividend); if (dividend == -2147483648) { if (divisor == -1) { return INT_MAX; } else if (divisor == 1) { return -2147483648; } } int ans = 0; while (lo <= hi) { unsigned long long int mid = (lo + hi)/2; if (abs(divisor)*mid <= abs(dividend)) { ans = mid; lo = mid + 1; } else { hi = mid -1 ; } } if ((divisor > 0 && dividend < 0) || (divisor < 0 && dividend > 0)) { return -ans; } else { return ans; } } };