# LeetCode - Divide Two Integers

## Problem statement

Given two integers `dividend`

and `divisor`

, divide two integers **without** using multiplication, division, and mod operator.

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

would be truncated to `8`

, and `-2.7335`

would be truncated to `-2`

.

Return *the quotient after dividing dividend by divisor.*

**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, if the quotient is **strictly greater than** 2^31 - 1, then return 2^31 - 1, and if the quotient is **strictly less than** -2^31, then return -2^31.

Problem statement taken from: https://leetcode.com/problems/divide-two-integers

**Example 1:**

```
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
```

**Example 2:**

```
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
```

**Constraints:**

```
- -2^31 <= dividend, divisor <= 2^31 - 1
- divisor != 0
```

### Explanation

#### Brute Force

We are not allowed to use multiplication, division, and mod operator. We can make use of the subtraction operator to divide two integers and find the answer. We keep subtracting the divisor from the dividend till the time dividend is greater than or equal to the divisor. We keep a count of the number of subtractions. This count is equal to the quotient of the two numbers.

We must also keep track of the sign of the dividend and the divisor. A C++ snippet of this approach is as follows:

```
int divide(int dividend, int divisor) {
if (divisor == 1)
return dividend;
if (dividend == INT_MIN) {
dividend++;
}
int sign = -1, quotient = 0;
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
dividend = abs(dividend);
divisor = abs(divisor);
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return quotient * sign;
}
```

The time complexity of this approach is **O(abs(m - n) / n)**, where m is the dividend and n is the divisor. The space complexity of this approach is **O(1)**. We are not using any extra space to store the numbers, the space complexity of this solution is constant, i.e. **O(1)**.

#### Binary Search

We can optimize the above approach using Binary Search. We know for a particular dividend and divisor, **quotient * divisor <= dividend**. For a number **a**, which is less than the quotient this equation always holds true **a * divisor <= dividend**. Similarly, for a number **b** which is greater than the quotient, the equation **b * divisor >= dividend** is true.

We know the quotient will lie between 0 and the dividend. We perform a binary search on this given range 0 to the dividend. If **mid * divisor > dividend**, we search the left side and set **high = mid - 1**. Else we search the right side and set **low = mid + 1**. The value of mid that satisfies the condition will be our quotient.

A C++ snippet of this approach is as follows:

```
int divide(int dividend, int divisor) {
unsigned long long int low = 0;
unsigned long long int high = abs(dividend);
if (dividend == INT_MIN) {
if (divisor == -1) {
return INT_MAX;
} else if (divisor == 1) {
return INT_MIN;
}
}
int quotient = 0;
while (low <= high) {
unsigned long long int mid = (low + high) / 2;
if (abs(divisor) * mid <= abs(dividend)) {
quotient = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0) ? quotient : -quotient);
}
```

The time complexity of this approach is **O(log n)**, where n is the dividend. The space complexity of this approach is **O(1)**.

#### Bit Manipulation

We find the greatest power of 2 when multiplied by the quotient gives us a quotient that is just smaller than the dividend. After finding this power, we add it to our answer. We then reduce the dividend by the divisor multiplied by this power of 2.

Let's check the algorithm to understand it clearly.

#### Algorithm

```
- if dividend == divisor
return 1
- set isPositive = (dividend < 0 == divisor < 0)
absDividend = abs(dividend)
absDivisor = abs(divisor)
answer = 0
- loop while absDividend >= absDivisor
int quotient = 0
loop while absDividend > (absDivisor << (quotient + 1))
quotient++
while end
update answer = answer + (1 << quotient)
update absDividend = absDividend - (absDivisor << quotient)
- while end
- if answer == (1 << 31) and isPositive
return INT_MAX
- return isPositive ? answer : -answer
```

The time complexity of this approach is **O(log n)**, where n is the dividend. The space complexity of this approach is **O(1)**.

Let's check out our solutions in **C++**, **Golang**, and **Javascript**.

#### C++ solution

```
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == divisor) {
return 1;
}
bool isPositive = (dividend < 0 == divisor < 0);
unsigned int absDividend = abs(dividend);
unsigned int absDivisor = abs(divisor);
unsigned int answer = 0;
while (absDividend >= absDivisor) {
int quotient = 0;
while (absDividend > (absDivisor << (quotient + 1)))
quotient++;
answer += (1 << quotient);
absDividend -= (absDivisor << quotient);
}
if (answer == (1 << 31) and isPositive)
return INT_MAX;
return isPositive ? answer : -answer;
}
};
```

#### Golang solution

```
func abs(a int) int {
if a < 0 {
return a * -1
}
return a
}
func divide(dividend int, divisor int) int {
if dividend == divisor {
return 1
}
isPositive := true
if (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) {
isPositive = false
}
absDividend := abs(dividend)
absDivisor := abs(divisor)
answer := 0
for absDividend >= absDivisor {
quotient := 0
for absDividend > (absDivisor << (quotient + 1)) {
quotient++
}
answer += (1 << quotient)
absDividend -= (absDivisor << quotient)
}
if answer == (1 << 31) && isPositive {
return math.MaxInt32
}
if isPositive {
return answer
} else {
return -answer
}
}
```

#### JavaScript solution

```
var divide = function(dividend, divisor) {
if (dividend == divisor) {
return 1;
}
let isPositive = (dividend < 0 == divisor < 0);
let absDividend = Math.abs(dividend);
let absDivisor = Math.abs(divisor);
let answer = 0;
while (absDividend >= absDivisor) {
let quotient = 0;
while (absDividend > (absDivisor << (quotient + 1)))
quotient++;
answer += (1 << quotient);
absDividend -= (absDivisor << quotient);
}
if (answer == (1 << 31) && isPositive)
return Number.MAX_SAFE_INTEGER;
return isPositive ? answer : -answer;
};
```

#### Dry Run

Let's dry-run our algorithm for a few examples to see how the solution works.

```
Input dividend = 10
divisor = 3
Step 1: if dividend == divisor
10 == 3
false
Step 2: isPositive = (dividend < 0 == divisor < 0)
= (10 < 0 == 3 < 0)
= (false == false)
= true
absDividend = abs(dividend)
= abs(10)
= 10
absDivisor = abs(absDivisor)
= abs(3)
= 3
answer = 0
Step 3: loop while absDividend >= absDivisor
10 >= 3
true
quotient = 0
loop while absDividend > (absDivisor << (quotient + 1))
10 > (3 << (0 + 1))
10 > (3 << 1)
10 > 6
true
quotient++
quotient = quotient + 1
= 1
loop while absDividend > (absDivisor << (quotient + 1))
10 > (3 << (1 + 1))
10 > (3 << 2)
10 > 12
false
answer += (1 << quotient)
answer = answer + (1 << quotient)
= 0 + 1 << 1
= 0 + 2
= 2
absDividend -= (absDivisor << quotient)
absDividend = absDividend - (absDivisor << quotient)
= 10 - (3 << 1)
= 10 - 6
= 4
Step 4: loop while absDividend >= absDivisor
4 >= 3
true
quotient = 0
loop while absDividend > (absDivisor << (quotient + 1))
4 > (3 << (0 + 1))
4 > (3 << 1)
4 > 6
false
answer += (1 << quotient)
answer = answer + (1 << quotient)
= 2 + 1 << 0
= 2 + 1
= 3
absDividend -= (absDivisor << quotient)
absDividend = absDividend - (absDivisor << quotient)
= 4 - (3 << 0)
= 4 - 3
= 1
Step 5: loop while absDividend >= absDivisor
1 >= 3
false
Step 6: if answer == (1 << 31) && isPositive
3 == 2147483648 && true
false && true
false
Step 7: return isPositive ? answer : -answer
true ? 3 : -3
We return the answer as 3.
```