Divide Two Integers

Easy
0/40
Average time to solve is 10m
profile
Contributed by
45 upvotes
Asked in companies
CognizantSnapdealSAP Labs

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
10 3
Sample Output 1:
3
Explanation of sample input 1:
Given ‘dividend = 10’ and ‘divisor = 3’

So the division is ‘10/3 = 3.3333……’.

Return only integer part ‘3’
Sample Input 2:
7 -3
Sample Output 2:
-2
Constraints:
-10^9 <= dividend, divisor <= 10^9 
divisor != 0  

Time limit: 1 second
Hint

Change multiplicative property as a subtraction.

Approaches (2)
Using Subtraction

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:

 

  1. Store the ‘IS_DIVIDEND_NEGATIVE = false’ and ‘IS_DIVISOR_NEGATIVE = false’.
  2. Check if the ‘DIVIDEND’ and ‘DIVISOR’ are positive or negative and update the values of ‘IS_DIVIDEND_NEGATIVE’ and  ‘IS_DIVISOR_NEGATIVE’.
  3. Iterate a while loop with ‘quotient = 0’
    • if ( ‘DIVIDEND’ > divisor) then:
      • (‘DIVIDEND’ = ‘DIVIDEND’ - ‘DIVISOR’) and (‘QUOTIENT’ = ‘QUOTIENT’  + 1).
  4. If both ‘IS_DIVIDEND_NEGATIVE’ and ‘IS_DIVISOR_NEGATIVE’ are of the same sign
    • Return ‘QUOTIENT’.
  5. Else, we need to make ‘quotient’ negative
    • Return ‘-1 * QUOTIENT’.
Time Complexity

0(N / M), where ‘N’ is ‘dividend’ and ‘M’ is ‘divisor’.

 

We are using a while loop, at max, it can iterate upto ‘dividend/divisor’ times.

Space Complexity

O(1).

 

Constant space is used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Divide Two Integers
Full screen
Console