Divide Two Integers | Leet Code

Given two integers dividend and divisor, divide them and output the quotient, without using multiplication, division and mode operator.

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 2³¹ − 1 when the division result overflows.

Examples

Input: Dividend = 10, Divisor = 3
Output = 3
Explanation: 10/3 = 3.333. So the answer is 3

Input: Dividend = 1542, Divisor = 17
Output = 90
Explanation: 1542/17 = 90.70. So the answer is 90.

Solution

Let us call the answer to the problem as ans (which is the quotient when you divide dividend by divisor)

Since ans is the quotient, following is true:

ans*divisor <= dividend.

Similarly, for any number x greater than ans, the following is true

x*divisor > dividend

And for any number y less than ans, the following is true

y*divisor < dividend

We can use the above properties to implement a solution using binary search.

If we remove the edge cases (we can handle them separately), we know that the quotient will be b/w 0 and dividend. Therefore, we can apply a binary search b/w 0 and dividend.

If the mid*divisor > dividend, then make go left and make hi = mid - 1, Otherwise save the mid and do low = mid + 1.

Solution Implementation

• C++

class Solution {
public:
    int divide(int dividend, int divisor) {
      unsigned long long int lo = 0;
      unsigned long long int hi = abs(dividend);
      if (dividend == -2147483648) {
        if (divisor == -1) {
          return INT_MAX;
        }
        else if (divisor == 1) {
          return -2147483648;
        }
      }
      int ans = 0;
      while (lo <= hi) {
        unsigned long long int mid = (lo + hi)/2;
        if (abs(divisor)*mid <= abs(dividend)) {
          ans = mid;
          lo = mid + 1;
        }
        else {
          hi = mid -1 ;
        }
      }
      if ((divisor > 0 && dividend < 0) || (divisor < 0 && dividend > 0)) {
        return -ans;
      }
      else {
        return ans;
      }
    }
};