Last Updated: 28 Jan, 2021
Divide Two Integers
Easy
Asked in companies
You are given two integers, ‘dividend’ and ‘divisor’.
You are required 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 integer value of the quotient which is closer to zero.
For example - If the answer is '8.34', we return the integer part, i.e., '8'. Also, If the answer is '-2.67', we return the integer part, i.e., '-2'.
Assume we're dealing with a system that can only store integers in the 32-bit signed integer range: [2^31, 2^31-1]. If the quotient is higher than 2^31 - 1, return 2^31 - 1; if it is less than -2^31, return -2^31.
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 input line contains two space-separated integers, ‘dividend’ and ‘divisor’.
Output Format
The only line contains the result after division, following the above rules.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
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’.
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’.