# 29. Divide Two Integers (Medium)

https://leetcode.com/problems/divide-two-integers/

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.

Example 1:

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

Example 2:

```Input: dividend = 7, divisor = -3
Output: -2```

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: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

## Solutions

``````class Solution {
/*
* This problem is really frustrating with a mass of corn cases.
* Interviewers much take good care of overflow issue. To get rid of overflow,
* It's a good habit to convert all the variables to long type before calculation.
*/
public int divide(int dividend, int divisor) {
// Be careful of the overflow issue
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}

if (divisor == 1) {
return dividend;
}

if (divisor == -1) {
return -dividend;
}

boolean isNegative = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0));

// do not use below statements, Math.abs can be handle int overflow issue
//            long tmpDvd = Math.abs(dividend);
//            long tmpDvs = Math.abs(divisor);

long tmpDvd = dividend;
long tmpDvs = divisor;

tmpDvd = Math.abs(tmpDvd);
tmpDvs = Math.abs(tmpDvs);

int ans = 0;

long remain = tmpDvd;
while (true) {
if (remain - tmpDvs < 0) {
break;
}

int count = 0;
// 1. comparision must be >= 0, not > 0
// 2. tmpDvs must be long type, otherwise overflow takes place
while (remain - (tmpDvs << count) >= 0) {
count++;
}

count--;

// to reach here, count must be >= 0

ans += (1 << count);

// notice remain - divisor << count is absolutely different from remain - (divisor << count)
remain -= tmpDvs << count;
}

return isNegative ? -ans : ans;
}
}
``````