## February LeetCoding Challenge 2021

Day 27

## Divide Two Integers

**PROBLEM STATEMENT:**

Given two integers

Return the quotient after dividing

The integer division should truncate toward zero, which means losing its fractional part. For example,

`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: [−2
^{31}, 2^{31}− 1]. For this problem, assume that your function**returns 2**.^{31}− 1 when the division result overflows

**Example 1**

Input:dividend = 10, divisor = 3Output:3Explanation:10/3 = truncate(3.33333..) = 3.

**Example 2**

Input:dividend = 7, divisor = -3Output:-2Explanation:7/-3 = truncate(-2.33333..) = -2.

**Example 3**

Input:dividend = 0, divisor = 1Output:0

**Example 4**

Input:dividend = 1, divisor = 1Output:1

**Constraints:**

`-2`

^{31}<= dividend, divisor <= 2^{31}- 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

- 50-4*2
^{0}= 46 - 50-4*2
^{1}= 42 - 50-4*2
^{2}= 34 - 50-4*2
^{3}, The next 50-4*2^{4}is not possible as it will be less than zero.

^{3}= 8 to our result. Subtracting 4*8 = 32 from 50 we are left with 18 (>4). We repeat the same process again.

- 18-4*2
^{0}= 14 - 18-4*2
^{1}= 10 - 18-4*2
^{2}= 2, The next 18-4*2^{3}will not be possible as it will be less than zero.

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

`50/4.`

We instead distributed the dividend as
`(4*2`^{3} + 4*2^{2} + 2) / 4

. That can be solved easily without using any division operations. Why powers of 2? well `2`^{i}

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*2`

.^{i} - Add 2
^{shift}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)

## code

## 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
```