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; } }