# Divide Two Integers | Leet Code

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: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 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;
}
}
};```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]