Leetcode: divide-two-integers

Question

I was practicing divide-two-integers question from leetcode

Question: 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.

Question Link: https://leetcode.com/problems/divide-two-integers/

For this I wrote the following algorithm but clearly it isn't optimized with my time complexity coming out to be about 8248 ms. Can someone please help me in optimizing the code?

 /**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
 let negativeFlag = false
 let quiotentHolder = 0 
 if (divisor === 0 || dividend === 0) return 0;
 if (dividend === -2147483648 && divisor === -1) return 2147483647;
 else if (dividend < 0 && divisor < 0) {
 dividend = -dividend
 divisor = -divisor
 } else if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
 negativeFlag = true
 divisor < 0 ? divisor = -divisor :dividend = -dividend
 }
 while (divisor <= dividend) {
 dividend = dividend - divisor
 quiotentHolder += 1
 }
 if (negativeFlag) return -quiotentHolder
 else return quiotentHolder
}

• slepic: number - number - number indeed equals -number, but why complicating it that much? :)
• iRohitBhatia: @slepic Updated code

Answer 1

Division by zero

Your implementation returns zero if you devide by zero. That is wrong. Division by zero is undefined.

if (divisor === 0 || dividend === 0) return 0;

On other hand, zero divided by nonzero is zero, that's ok. But zero divided by zero is still undefined. And so it should be checked first.

if (divisor === 0) throw "Division by zero";
if (dividend === 0) return 0;

Edge cases

For some reason you are checking combination -2147483648/-1 then you claim it is 2147483647, but that's wrong. Firstly, 2147483648 is representable in js number type. But if you consider it overflow, you should throw overflow error.

if (dividend === -2147483648 && divisor === -1) throw 'Overflow error';

Btw notice, that -2147483648/n would also overflow further in your code because you convert dividend and divisor to positives. And so maybe you should throw overflow error in this case as well no matter the divisor.

if (dividend === -2147483648) throw 'Overflow error';

Simplify conditions

There is unnecesarily complex condition:

(dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)

assuming the first if was already executed, then the eleseif condition can be simplified as

dividend < 0 || divisor < 0

Or even better, split it in two elseifs, because you have a ternary that checks again.

if (dividend < 0 && divisor < 0) {
 dividend = -dividend
 divisor = -divisor
} else if (dividend < 0) {
 negativeFlag = true
 dividend = -dividend;
} else if (divisor < 0) {
 negativeFlag = true
 divisor = -divisor;
}

Notice that I omitted zeroes, because they have been excluded in the beginning.

Negative flag

This flag is unnecesary, you could instead have an integer variable with value of +1 or -1.

let quotientUnit = 1;
if (...) quotientUnit = -1;
let quiotentHolder = 0;
while (divisor <= dividend) {
 dividend -= divisor; //notice -=
 quiotentHolder += quotientUnit;
}
return quiotentHolder;

Performance

Just of curiosity, have you tried something like big/small. Is it fast? It seems to me the bigger the result of the division, the more time consuming your algorithm is... Not sure if there is a faster way though. Division without division is not something I usualy think of :) But I could suppose there is not, because that's why we have division optimized in our CPUs, where it can be fastened by paralel processing (by which i mean paralel nature of logic gates, not running multiple threads inside a CPU)

EDIT: You mentioned that your "time complexity is about 8248 ms". Firstly, time complexity is not a meassure of time. Time complexity is more like a meassure of relative time consumption based on the size of the input. Since in your case there is no "size of input", time complexity makes no sense with this algorithm. If you wanted to define something like time complexity for your algorithm, it would probably be something like O(dividend/divisor), but this is not really a time complexity, but I am still able to make sense of it...

But let's suppose you meant the actual run time. Not sure what input does the 8248 ms refer to. As I said, the speed is different for different inputs.

• JollyJoker: Maybe some kind of arr[n] = arr[n-1] + arr[n-1] loop to build a list of powers of two times the divisor, then subtract them from the dividend starting with the largest?

Answer 2

I did a recursive solution using powers of two times the divisor. Essentially, it finds the highest divisor * 2^n that still fits in the dividend, subtracts it and repeats.

const divide = (dividend, divisor) => {
 if (dividend === -2147483648 && divisor === -1) return 2147483647;
 const result = dividePositive(Math.abs(dividend), Math.abs(divisor))
 return dividend < 0 === divisor < 0 ? result : 0 - result
};
const dividePositive = (dividend, divisor) => {
 if(dividend < divisor) return 0
 let subtract = divisor, result = 1
 while(subtract < dividend-subtract) {
 subtract += subtract
 result += result
 }
 return result + dividePositive(dividend-subtract, divisor)
}

I've tried tricks like using subtract <<= 1 instead of subtract += subtract, having an extra while loop instead of the recursion, saving the powers of two in tables etc. but never achieved anything that would be noticeably faster.

For reference, a version saving the intermediate results if you want to tweak further. Note that n <<= 1 flips around to negative numbers at 2^32, giving you a bit of a headache with handling high numbers.

var divide = function(dividend, divisor) {
 if (dividend === -2147483648 && divisor === -1) return 2147483647;
 flipSign = dividend < 0 != divisor < 0
 dividend = Math.abs(dividend);
 divisor = Math.abs(divisor);
 var subtract = divisor, result = 1
 powers = [], results = []
 while(subtract <= dividend) {
 powers.push(subtract)
 results.push(result)
 subtract += subtract;
 result += result;
 }
 final = 0;
 for(var i = powers.length -1; i >= 0; i--) {
 if(dividend >= powers[i]) {
 dividend -= powers[i];
 final += results[i];
 }
 }
 return flipSign ? 0 - final : final
};

Copy paste the code to https://leetcode.com/problems/divide-two-integers/ and submit to run and get the time results.

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.