Divide Two Integers Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Oracle Uber Yahoo
Bit Manipulation Math Riot GamesViews 6339

Problem Statement

The Divide Two Integers LeetCode Solution – “Divide Two Integers” states that you’re given two integers dividend and divisor. Return the quotient after dividing the dividend by the divisor.

Note that we’re assuming that we’re dealing with an environment that could store integers within a 32-bit signed integer range.

Example:

Input:  dividend = 10, divisor = 3
Output: 3

Explanation:

  • On dividing 10 by 3, we get 3.3333…
  • Truncate the above value, we get 3 as our answer.
Input:  dividend = 7, divisor = -3
Output: -2

Explanation:

  • On dividing 7 by -3, we get -2.33333…
  • Truncate the above value, we get -2 as our answer.

Approach

Idea:

  1. The main idea to solve this problem is to use Bit Manipulation.
  2. First, we need to write corner cases, since we’re dealing in an environment where we have numbers in the 32-bit range.
  3. Corner Cases are:
    1. If the dividend is INT_MIN, and the divisor is 1, the answer is INT_MIN.
    2. If the dividend is INT_MIN, and the divisor is -1, the answer is INT_MAX.
    3. If the divisor is INT_MIN, return 0.
  4. The key observation is that the quotient of a division is just the number of times that we can subtract the divisor from the dividend without making it negative.
  5. Note that when a dividend is INT_MIN:
    1. If the divisor is odd, increase the dividend by 1.
    2. If the divisor is even, divide both dividend and divisor by 2.
  6. Doing the above operations won’t change the quotient.
  7. Check out the code for detailed analysis.

Code

Divide Two Integers Leetcode C++ Solution:

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==INT_MIN and divisor==1){
            return INT_MIN;
        }
        if(dividend==INT_MIN and divisor==-1){
            return INT_MAX;
        }
        if(dividend==INT_MIN and divisor&1){
            return divide(dividend+1,divisor);
        }
        if(dividend==INT_MIN and divisor%2==0){
            return divide(dividend/2,divisor/2);
        }
        
        if(divisor==INT_MIN){
            return 0;
        }
        
        int sign = 1,ans = 0;
        if((dividend>0 and divisor<0) or (dividend<0 and divisor>0)){
            sign = -1;
        }
        
        divisor = abs(divisor);
        dividend = abs(dividend);
        
        while(dividend>=divisor){
            int curr = divisor,shift = 0;
            while(curr<=(INT_MAX)/2 and dividend>=curr*2){
                shift++;
                curr *= 2;
            }
            dividend -= curr;
            ans += (1<<shift);
        }
        
        return ans*sign;
    }
};

Divide Two Integers Leetcode Java Solution:

class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor==0||dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
        int res=0;
        int sign=(dividend<0)^(divisor<0)?-1:1;
        long dvd=Math.abs((long)dividend);
        long dvs=Math.abs((long)divisor);
        while(dvs<=dvd){
            long temp=dvs,mul=1;
            while(dvd>=temp<<1){
                temp<<=1;mul<<=1;
            }
            dvd-=temp;res+=mul;
        }
        return sign==1?res:-res;
    }
}

Complexity Analysis for Divide Two Integers Leetcode Solution

Time Complexity

The time complexity of the above code is O(log(N)*log(N)) since the outer loop and the inner loop both runs log(N) times, where N is the dividend.

Space Complexity

The space complexity of the above code is O(1) since we’re using constant extra space.

Translate »