###### Divide Two Integers | February Leetcoding challenge 2021 | Day 27
Manas Sinha
Developer | Designer

## Divide Two Integers

`PROBLEM  STATEMENT:`
Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division, and mod operator.
Return the quotient after dividing `dividend` by `divisor`.
The integer division should truncate toward zero, which means losing its fractional part. For example, `truncate(8.345) = 8` and `truncate(-2.7335) = -2`.
Note:
• Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
Example 1
```Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
```
Example 2
```Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
```
Example 3
```Input: dividend = 0, divisor = 1
Output: 0
```
Example 4
```Input: dividend = 1, divisor = 1
Output: 1
```
Constraints:
• `-231 <= dividend, divisor <= 231 - 1`
• `divisor != 0`

## Explanation

The naive approach would be to just subtract the divisor from the dividend while the dividend is bigger than the divisor.But boy! could that be more slow. So, we improvise :D.
Instead of subtracting divisor linearly, we subtract it exponentially. See the following example:
• Dividend = 50
• Divisor = 4
We solve it in the following way:
• 50-4*20 = 46
• 50-4*21 = 42
• 50-4*22 = 34
• 50-4*23 , The next 50-4*24 is not possible as it will be less than zero.
We can add 23 = 8 to our result. Subtracting 4*8 = 32 from 50 we are left with 18 (>4). We repeat the same process again.
• 18-4*20 = 14
• 18-4*21 = 10
• 18-4*22 = 2, The next 18-4*23 will not be possible as it will be less than zero.

We can add 22 = 4 to our result. Subtracting 4*4 = 16 from 18 we are left with 2 (<4). So we can terminate now.

To be more clear, we had to find `50/4.` We instead distributed the dividend as `(4*23 + 4*22 + 2) / 4`. That can be solved easily without using any division operations. Why powers of 2? well `2i` can easily be found using shift operators.
`ALGORITHM: `
• First we take care of some boundary conditions (see the code). And also find the out the sign of the final answer. Store it in a sign variable.
• Take the absolute value of both dividend and divisor as dd and dr respectively.
• Initialise the result variable with zero.
• While dd >= dr<<(shift+1) we increase the shift variable by 1. For people who are wondering, ` a << i ` is equal to `a*2i`.
• Add 2shift to result which is essentially `res += (1 << shift)`.
• Decrement `dr << shift` from dd.
• Repeat the process until dd >= dr.
• Return sign*res
• Since the divisor is increasing exponentially, the time complexity will be O(log n).
• Space complexity : O(1)

## C++

``````class Solution {
public:
int divide(int dividend, int divisor) {
if(!divisor) return INT_MAX;

bool sign = (dividend>0 && divisor<0) || (dividend<0 && divisor>0);
if(dividend == INT_MIN && divisor == -1) return INT_MAX;
long int ldd = abs(dividend) , ldr = abs(divisor);
if(ldr == 1) return sign ? -ldd : ldd;

int res = 0;

while(ldd >= ldr){
int shift = 0;
while(ldd >= ldr<<(shift+1))
shift++;

res += 1<<shift;
ldd -= ldr<<shift;
}

return sign ? -res : res;

}
};``````

## PYTHON

``````MAX = 2147483647
MIN = -2147483648
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
#taking care of corner cases
if not divisor:
return MAX

if dividend == MIN and divisor == -1:
return MAX

#----------------------------

sign = -1 if (dividend>0 and divisor<0) or (dividend<0 and divisor>0) else 1

dd = abs(dividend)
dr = abs(divisor)

res = 0

while dd >= dr:
shift = 0
while dd >= dr<<(shift+1):
shift +=1

res += 1<<shift
dd -= dr<<shift
return sign*res``````