# Divide Two Integers

Posted: 28 Jan, 2021

Difficulty: Easy

#### You are given two integers ‘dividend’ and ‘divisor’. You are required is to divide the integers without using multiplication, division and modular operators. Your task is to return the quotient after dividing ‘dividend’ by ‘divisor’.

#### Note :

```
In cases where the dividend is not perfectly divisible by the divisor, you are required to return the floored value of the quotient.
```

#### For example :

```
If the answer is ‘9.333’ then return ‘9’ or if the answer is ‘-8.123’ then return ‘-8’.
```

##### Input format:

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first line of every test case contains two space-separated integers ‘dividend’ and ‘divisor’.
```

##### Output Format

```
For each test case, return the floor value of the quotient.
Output for each test case will be printed in a separate line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10^5
-10^9 <= dividend, divisor <= 10^9
divisor != 0
Time limit: 1 second
```

Approach 1

We can subtract the divisor from the dividend until the dividend is greater than the divisor. The quotient will be equal to the number of total subtractions performed.

**Below is the detailed algorithm:**

- Store the ‘IS_DIVIDEND_NEGATIVE = false’ and ‘IS_DIVISOR_NEGATIVE = false’.
- Check if the ‘DIVIDEND’ and ‘DIVISOR’ are positive or negative and update the values of ‘IS_DIVIDEND_NEGATIVE’ and ‘IS_DIVISOR_NEGATIVE’.
- Iterate a while loop with ‘quotient = 0’
- if ( ‘DIVIDEND’ > divisor) then:
- (‘DIVIDEND’ = ‘DIVIDEND’ - ‘DIVISOR’) and (‘QUOTIENT’ = ‘QUOTIENT’ + 1).

- if ( ‘DIVIDEND’ > divisor) then:
- If both ‘IS_DIVIDEND_NEGATIVE’ and ‘IS_DIVISOR_NEGATIVE’ are of the same sign
- Return ‘QUOTIENT’.

- Else, we need to make ‘quotient’ negative
- Return ‘-1 * QUOTIENT’.

Approach 2

In this case quotient is = ‘2^3 + 2^2 +2^0 =13 = floor(107/8)’.

The intuition here is that we can find the largest power of 2’s which can satisfy the equation ‘dividend = divisor * maximum 2’s power + remainder’.

If found we set ‘quotient’ to ‘quotient = quotient + maximum 2’s power’.

Below is the detailed algorithm:

- Store the ‘IS_DIVIDEND_NEGATIVE = false’ and ‘IS_DIVISOR_NEGATIVE = false’.
- Check if the 'DIVIDEND' and 'DIVISOR' are positive or negative and update the values of ‘IS_DIVIDEND_NEGATIVE’ and ‘IS_DIVISOR_NEGATIVE’.
- Use variable ‘QUOTIENT = 0’.
- Iterate a loop from ‘31’ to ‘0’ with ‘-1’ jumps (say iterator = ‘i’):
- If ( 'DIVISOR' << i <= 'DIVIDEND')
- Then ‘QUOTIENT = QUOTIENT + 1 << i’ and ‘DIVIDEND = DIVIDEND - DIVISOR << i’.

- If ( 'DIVISOR' << i <= 'DIVIDEND')
- If both ‘IS_DIVIDEND_NEGATIVE’ and ‘IS_DIVISOR_NEGATIVE’ are of the same sign:
- Return ‘QUOTIENT’

- Else, we need to make ‘QUOTIENT’ negative:
- Return ‘-1 * QUOTIENT’.

SIMILAR PROBLEMS

# Palindromes And Indexes

Posted: 7 Jul, 2021

Difficulty: Moderate

# Ceiling in a sorted array

Posted: 8 Jul, 2021

Difficulty: Moderate

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Find All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy

# Subset OR

Posted: 31 Jul, 2021

Difficulty: Moderate