In the Leetcode Divide Two Integers problem solution 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 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
- -231 <= dividend, divisor <= 231 – 1
- divisor != 0
Solution in C Programming
#include<limits.h>
#include<stdlib.h>
int divide(int dividend, int divisor){
// Check if the quotient will be positive or negative
int isPositive = 1;
// If both dividend and divisor are negative, quotient will be positive
if(dividend<0 && divisor<0) isPositive = 1;
// If either one of the dividend or the divisor is negative, quotient will be negative
else if(dividend<0 || divisor<0) isPositive = 0;
// Convert to long to handle the overflow conditions
long new_dividend = dividend, new_divisor = divisor;
// Extracts the absolute value of both. Was not working with with the inbuilt abs() functions, hence subtracted from 0 if negative.
if(new_dividend<0) new_dividend = 0 - new_dividend;
if(new_divisor<0) new_divisor = 0 - new_divisor;
// Core logic, using shift operations and dividing the dividend by doubling the divisor in every iteration
long temp,i;
long res = 0;
while(new_dividend>=new_divisor){
i = 1;
temp = new_divisor;
while(new_dividend>=temp){
new_dividend -= temp;
res += i;
i = i<<1;
temp = temp<<1;
}
}
// Check if final answer should be +ve or -ve based on the original sign of dividend and divisor
if(!isPositive) res = 0-res;
// Return either INT_MIN or INT_MAX or the result accordingly
if(res>INT_MAX)
return(INT_MAX);
else if(res<INT_MIN)
return(INT_MIN);
else
return(res);
}Solution in C++ Programming
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor == 0) return INT_MAX;
if (divisor == -1 && dividend == INT_MIN) return INT_MAX;
int negative = ((dividend > 0) ^ (divisor > 0));
long dd = abs((long) dividend), ds = abs((long) divisor);
long current =1,ans=0;
do {
ds <<= 1;
current <<= 1;
}while (dd >= ds);
while (current!=0) {
if ( dd >= ds) {
dd -= ds;
ans |= current;
}
current >>= 1;
ds >>= 1;
}
return negative? -ans:ans;
}
};Solution in Java Programming
class Solution {
public int divide(int dividend, int divisor) {
int sign = 1;
if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0)
sign = -1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
if (ldividend>Integer.MAX_VALUE && divisor==-1)
return Integer.MAX_VALUE;
if (ldividend == 0 || ldividend < ldivisor || ldivisor==0)
return 0;
int ans=0;
while(ldividend >= ldivisor) {
long sum = ldivisor;
long multiple = 1;
while (sum+sum <= ldividend) {
sum += sum;
multiple += multiple;
}
ans+=multiple;
ldividend-= sum;
}
return ans*sign;
}
}Solution in Python Programming
class Solution(object):
def divide(self, dividend, divisor):
if divisor == 0:
return 0
if dividend == 0:
return 0
positive = (dividend > 0) is (divisor > 0)
dividend = abs(dividend)
divisor = abs(divisor)
res = 0
while dividend >= divisor:
d, i = divisor, 1
while (d << 1) < dividend:
d = d << 1
i = i << 1
dividend = dividend - d
res += i
if not positive:
res = -res
return min(max(-2147483648, res), 2147483647)Solution in C# Programming
public class Solution
{
public int Divide(int dividend, int divisor)
{
checked
{
if (dividend == 0)
{
return 0;
}
long res = 0;
bool positive = true;
long lDividend = dividend;
long lDivisor = divisor;
if (dividend > 0 && divisor < 0)
{
positive = false;
}
else if (dividend < 0 && divisor > 0)
{
positive = false;
}
if (dividend < 0)
{
lDividend = -lDividend;
}
if (divisor < 0)
{
lDivisor = -lDivisor;
}
if (lDivisor == 1)
{
res = lDividend;
}
else
{
int shift = 1;
while (true)
{
while (true)
{
if (lDividend >= lDivisor || shift == 1)
{
break;
}
lDivisor = lDivisor >> 1;
shift = shift >> 1;
}
if (lDividend < lDivisor && shift == 1)
{
break;
}
lDividend -= lDivisor;
res += shift;
if (shift < 16)
{
shift = shift << 1;
lDivisor = lDivisor << 1;
}
}
}
try
{
if (!positive)
{
res = -res;
}
var output = (int) res;
return output;
}
catch (OverflowException)
{
return int.MaxValue;
}
}
}
}Also read,