Divide Two Integers | February Leetcoding challenge 2021 | Day 27
logo
Manas Sinha
Developer | Designer

By Manas | 27 February 2021

February LeetCoding Challenge 2021

Day 27

Divide Two Integers

PROBLEM  STATEMENT:
Given two integers 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: [−231,  231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
Example 1
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
Example 3
Input: dividend = 0, divisor = 1
Output: 0
Example 4
Input: dividend = 1, divisor = 1
Output: 1
Constraints:
  • -231 <= dividend, divisor <= 231 - 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
We solve it in the following way:
  • 50-4*20 = 46
  • 50-4*21 = 42
  • 50-4*22 = 34
  • 50-4*23 , The next 50-4*24 is not possible as it will be less than zero.
We can add 23 = 8 to our result. Subtracting 4*8 = 32 from 50 we are left with 18 (>4). We repeat the same process again.
  • 18-4*20 = 14
  • 18-4*21 = 10
  • 18-4*22 = 2, The next 18-4*23 will not be possible as it will be less than zero.

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

To be more clear, we had to find 50/4. We instead distributed the dividend as (4*23 + 4*22 + 2) / 4. That can be solved easily without using any division operations. Why powers of 2? well 2i 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*2i.
  • Add 2shift 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

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply