Hoarding programming problems for you!

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Divide two integers

Sharing is caring!

Problem statement
Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

Solution
Obviously the naive approach to this problem would be to subtract the divisor from the dividend until the dividend becomes less than the divisor, while keeping track of how many times we subtracted.

This approach is not optimal. Imagine you would have to divide 2147483648 by 1.

This problem can be solved based on the fact that any number can be converted to the format of the following:

num = a_0 \times 2^0 + a_1 \times 2^1 + a_2 \times 2^2 + \dots + a_n \times 2^n

So, we will increment our divisor by shifting it one position left at a time until it surpasses the divided. That is, multiply it by 2, by 4, by 8, etc. We then shift it one position to the right to get the maximum divisor that still fits in our divided and subtract that from our current dividend. We repeat the process for the rest of our dividend until it becomes smaller than our original divisor.

Example, let dividend = 14 = 1110 and divisor = 1. We start by taking our divisor and shift it one position to the left, making it divisor = 2. It still is less than or equal to 14. We continue by shifting it another position to the left, making it divisor = 4, still less than 14. We do another shift and make it divisor = 8, which is still less than 14. Finally, we shift it once more resulting in a divisor = 16, which is greater than our dividend = 14. Shifting it one position to the right will give us the largest divisor that fits into 14, which is 8 and subtract that from our divided. We keep track of our multiplication factor and add it to our answer – three shifts to the left results in a factor of 8. Our answer becomes 8.

We continue with the rest of the dividend which is 14 - 8 = 6. Our divisor is larger than 6, so we shift it one position to the left making it divisor = 2. We then shift it again making it divisor = 4 and finally another shift, resulting in a divisor = 8, which is larger than 6. Shifting it one position to the right will give us the largest divisor that fits into 6, which is 4 and subtract that from our divided.. We keep track of our multiplication factor and add it to our answer – two shifts to the left results in a factor of 4. Our answer becomes 12.

We continue with the rest of the dividend which is 6 - 4 = 2. Our divisor is larger than 2, so we shift it one position to the left making it divisor = 2. We then shift it again making it divisor = 4 which is larger than 2. Shifting it one position to the right will give us the largest divisor that fits into 2, which is 2 and subtract that from our divided. We keep track of our multiplication factor and add it to our answer – one shift to the left results in a factor of 2. Our answer becomes 14, which is also our final answer.

Full code