Solution For Divide Two Integers
Problem statement:
Given two integers dividend and divisor, divide the dividend by the divisor and return the quotient.
Assume that the dividend is bound to be a 32-bit signed integer (-231 <= dividend <= 231 – 1), and the divisor is a positive integer.
Return the floor of the integer division. That is, truncating the remainder. For example, 7/3 = 2 and 10/2 = 5.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33) = 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33) = -2.
Solution:
We can solve this problem using binary search. Let’s consider an example, dividend = 15 and divisor = 3. The quotient should be 5 i.e. 15/3 = 5. We can find the answer by continuously subtracting the divisor from the dividend until the dividend becomes less than the divisor. The number of times the divisor is subtracted gives us the quotient. This approach takes O(dividend) time in the worst case.
An optimized approach is to use binary search where we repeatedly divide the dividend by the divisor until either dividend becomes less than the divisor or equal to zero. The number of times divisor is divided gives us the quotient. The time complexity of the binary search approach is O(log(dividend)).
Algorithm:
We declare variables for the dividend and divisor.
We find the signs of the dividend and divisor. i.e. is the quotient going to be positive or negative.
We take the absolute values of the dividend and divisor.
We declare 3 variables for the quotient, left, and right.
We run a while loop until the dividend is greater than or equal to the divisor.
We check if divisor is greater than dividend/2. If it is, then we cannot subtract it anymore, so we break the loop.
We set left to 1 and right to dividend.
We run a binary search while left is less than or equal to right.
We find the mid-point of left and right.
We check if mid*divisor is greater than the dividend. If it is, we update right to mid – 1.
Else, we update left to mid + 1 and quotient to mid.
We return the quotient with the sign.
Code:
“`
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend == 0:
return 0
sign = (dividend < 0) == (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
quotient = 0
while dividend >= divisor:
if divisor > dividend/2:
break
left, right = 1, dividend
while left <= right:
mid = (left + right) // 2
if mid * divisor > dividend:
right = mid - 1
else:
quotient = mid
left = mid + 1
dividend -= quotient * divisor
if sign:
return min(quotient, 2**31-1)
else:
return max(-quotient, -2**31)
“`
Step by Step Implementation For 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.
*/
class Solution {
public int divide(int dividend, int divisor) {
// edge case: overflow
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
// edge case: dividend is 0
if (dividend == 0) {
return 0;
}
// convert to long type to avoid integer overflow
long dvd = (long) dividend;
long dvs = (long) divisor;
// get sign of the quotient
boolean sign = (dvd > 0 && dvs > 0) || (dvd < 0 && dvs < 0);
// make dvd and dvs absolute
dvd = Math.abs(dvd);
dvs = Math.abs(dvs);
// quotient
int quotient = 0;
// loop through all bits of the dividend
for (int i = 31; i >= 0; i--) {
// if the divisor can be subtracted from dividend
// without making it negative
if ((dvd >> i) - dvs >= 0) {
// update quotient with the max value of 2^i
quotient += 1 << i;
// update dividend
dvd -= dvs << i;
}
}
// if the quotient should be negative, make it so
if (!sign) {
quotient = -quotient;
}
return quotient;
}
}def divide(dividend, divisor): if dividend == 0: return 0 if divisor == 0: return None sign = 1 if dividend < 0 and divisor > 0: sign = -1 elif dividend > 0 and divisor < 0: sign = -1 dividend = abs(dividend) divisor = abs(divisor) res = 0 while dividend >= divisor: dividend -= divisor res += 1 return sign * res
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
// handle edge case where divisor is 0
if (divisor === 0) {
return undefined;
}
// determine sign of the quotient
let sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
// remove absolute values of dividend and divisor
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
// initialize quotient
let quotient = 0;
// as long as dividend is greater than or equal to divisor
while (dividend >= divisor) {
// determine number of times divisor goes into current dividend
let numTimes = 0;
let currentDividend = dividend;
while (currentDividend >= divisor) {
currentDividend -= divisor;
numTimes++;
}
// update quotient
quotient += numTimes;
// update dividend to be remainder
dividend = currentDividend;
}
// return quotient with sign
return sign * quotient;
};class Solution {
public:
int divide(int dividend, int divisor) {
// handle special cases
if (divisor==0)
return INT_MAX;
if (divisor==-1 && dividend == INT_MIN)
return INT_MAX;
// reduce the problem to positive long division
long pDividend = abs((long)dividend);
long pDivisor = abs((long)divisor);
int result = 0;
while (pDividend>=pDivisor) {
// calculate number of left shifts
int numShift = 0;
while (pDividend>=(pDivisor<0 && divisor>0) || (dividend<0 && divisor<0)) {
return result;
} else {
return -result;
}
}
}; /**
* 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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
*
* Example 1:
*
* Input: dividend = 10, divisor = 3
* Output: 3
* Explanation: 10/3 = truncate(3.33333..) = 3.
* Example 2:
*
* Input: dividend = 7, divisor = -3
* Output: -2
* Explanation: 7/-3 = truncate(-2.33333..) = -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.
*/
public class Solution {
public int Divide(int dividend, int divisor) {
// edge case: overflow
if (dividend == int.MinValue && divisor == -1) {
return int.MaxValue;
}
// edge case: dividend is 0
if (dividend == 0) {
return 0;
}
// convert to long to avoid integer overflow
long ldividend = (long) dividend;
long ldivisor = (long) divisor;
// take care of signs
bool isNegative = (ldividend < 0) != (ldivisor < 0);
ldividend = Math.Abs(ldividend);
ldivisor = Math.Abs(ldivisor);
// base case
if (ldividend < ldivisor) {
return 0;
}
// get highest bit of divisor
int shift = 0;
while ((ldivisor << shift) <= ldividend) {
shift++;
}
// dividend - (divisor * 2^(shift - 1))
long result = 0;
shift--;
while (shift >= 0) {
if ((ldividend >> shift) >= ldivisor) {
result += 1L << shift;
ldividend -= ldivisor << shift;
}
shift--;
}
return isNegative ? (int) -result : (int) result;
}
}