Divide Two Integers Problem: Given two integers dividend
and divisor
, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345
would be truncated to 8
, and -2.7335
would be truncated to -2
.
Return the quotient after dividing dividend
by divisor
.
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, if the quotient is strictly greater than 231 - 1
, then return 231 - 1
, and if the quotient is strictly less than -231
, then return -231
.
Example :
Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = 3.33333.. which is truncated to 3.
Table of Contents
Divide Two Integers Problem Solution
Problem Solution In Python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend*divisor>0:
res=abs(dividend)//abs(divisor)
else:
res=-(abs(dividend)//abs(divisor))
intmin=-(2**31)
intmax=(2**31)-1
return res if intmin<=res<=intmax else intmax
Problem Solution In Java
public int divide(int dividend, int divisor) {
boolean sign = true;
long dividendL = dividend;
long divisorL = divisor;
if (dividendL < 0) {
sign = !sign;
dividendL = -dividendL;
}
if (divisorL < 0) {
sign = !sign;
divisorL = -divisorL;
}
List<long[]> memo = new ArrayList<>(); // the size of the list is at most 32. So it is O(1) space.
long sum = divisorL;
long mult = 1;
memo.add(new long[]{sum, mult});
while ( sum + sum <= dividendL ) {
sum += sum;
mult += mult;
long[] current = {sum, mult};
memo.add(current);
}
long res = 0;
for (int i = memo.size() - 1; i >= 0; i--) {
if (dividendL - memo.get(i)[0] >= 0) {
dividendL -= memo.get(i)[0];
res += memo.get(i)[1];
}
}
if (!sign) res = -res;
if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
else return (int) res;
}
Problem Solution In C++
class Solution {
public:
int divide(int dividend, int divisor) {
bool negative = (dividend > 0) ^ (divisor > 0);
if(dividend == INT_MIN && divisor == -1) return INT_MAX;
if(dividend > 0) dividend = -dividend;
if(divisor > 0) divisor = -divisor;
int mul = divideHelper(dividend, divisor);
return negative ? mul : -mul;
}
private:
int divideHelper(int dividend, int divisor) {
if(dividend > divisor) return 0;
int mul = -1;
int sum = divisor;
while(sum >= dividend - sum) {
mul += mul;
sum += sum;
if(sum > 0) break;
}
return mul + divideHelper(dividend-sum, divisor);
}
};
Problem Solution In C
int divide(int dividend, int divisor){
int is_negative = (dividend > 0) ^ (divisor > 0);
long long ll_dividend = dividend;
long long ll_divisor = divisor;
long long quotient = 1;
ll_dividend = llabs(ll_dividend);
ll_divisor = llabs(ll_divisor);
long long sum = ll_divisor;
while (sum < ll_dividend) {
sum <<= 1;
quotient <<= 1;
}
while (sum > ll_dividend)
{
sum -= ll_divisor;
quotient--;
}
if (is_negative) {
quotient = -quotient;
}
if (quotient < INT_MIN || quotient > INT_MAX)
{
return INT_MAX;
}
return quotient;
}