Daily LeetCode Challenge (Day 13) #29. Divide Two Integers

Photo by Joshua Reddekopp on Unsplash

Difficulty | Medium

Challenge

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

Pseudo Code

• Back to elementary school principles of division & multiplication
• Think of multiplication as just a * b = c. This can be rewritten as a + a + a + … + a + a = c where a is repeated b times.
• think of division as a / b = c. this can be written as a-a-a-a-a-…-a = c.
• Using this fact we could keep subtracting a from c until c is too small, but this will take too long for large numbers.
  inorder to speed this up, we can double the total number of a’s we can subtract, there by making large calculations instead of linear ie we check if can subtract one a, then 2 a’s then 4 a’s then 8 a’s until we cant subtract anymore

Solution

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {

    // check if values are negative
     const isNegative = Math.sign(divisor) !== Math.sign(dividend);

// get absolute values
     dividend = Math.abs(dividend);
     divisor = Math.abs(divisor);

    let result = 0;

    while(divisor <= dividend){
        let value = divisor;
        let multiple = 1;

        while( value + value <= dividend){
            value += value;
            multiple +=multiple;
        }

        dividend = dividend - value;
        result += multiple

    }

    if(result > ((2**31) - 1)){
        return isNegative ? -(2**31) : 2**31 -1
    } 

    return isNegative ? -result : result;

};

Notes:

Its about keeping it simple and understanding the algorithm, thats the secret. there are more complicated ways, but heey.. simplicity is the ultimate sophistication

Happy Coding!