Divide Two Integers

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:

  1. We declare variables for the dividend and divisor.

  2. We find the signs of the dividend and divisor. i.e. is the quotient going to be positive or negative.

  3. We take the absolute values of the dividend and divisor.

  4. We declare 3 variables for the quotient, left, and right.

  5. We run a while loop until the dividend is greater than or equal to the divisor.

  6. We check if divisor is greater than dividend/2. If it is, then we cannot subtract it anymore, so we break the loop.

  7. We set left to 1 and right to dividend.

  8. 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.

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


Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]