Divide Two Integers Problem

Problem

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: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

Examples

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.

Solution

Method 1 - Using Binary Shifts

We know:

dividend = (quotient) * divisor + remainder

We need to find the quotient given the divisor and dividend.

Any number can be represented in binary form:

num = a_0*2^0 + a_1*2^1 + a_2*2^2 + ... + a_n*2^n

Same goes for quotient . Let us have an example: 58/5:

58 = (11) * 5 + 3

In binary, this quotient is ( $(11)_{10} = (1011)_2$ ):

58 = (2^3 + 2^1 + 2^0) * 5 + 3                // --- (I)
58 = [(2^3 * 5) + (2^1 * 5) + (2^0 * 5)] + 3  // --- (II)

We are given the equation 58 = q * 5 + rem and need to find q.

First, multiply 5 by powers of 2 until the result exceeds the dividend. Since multiplication operator is not allowed, we use bitwise left shift for multiplication:

5 << 0 = 5               // less than dividend
5 << 1 = 10              // less than dividend
5 << 2 = 20              // less than dividend
5 << 3 = 40              // less than dividend
5 << 4 = 5*2*2*2*2 = 80  // exceeds divided, so stop and consider previous value

We observe that:

58 = (2^3 * 5) + (something * 5) + rem // --- (III)

You can see we are getting close to the equation we initialy wanted (eqa II).

Since 5 is multiplied by (2^3), we add (2^3) to our answer and update the dividend:

 58 - (2^3 * 5) = 18 = something * 5 + rem

Further operating on equation III:

58 - (2^3 * 5)  =  (something * 5) + rem
58 - (8 * 5) = something * 5 + rem
58 - 40 = something * 5 + rem
18 = something * 5 + rem

What we effectively have done is, subtracted the result we got from our first step from dividend (58 - 40). We arived at the same question again but with a smaller dividend this time. dividend = 18, divisor = 5

Therefore let us repeat the process:

5 << 0 = 5           // less than dividend
5 << 1 = 5*2 = 10    // less than dividend
5 << 2 = 5*2*2 = 20  // exceeds divided, so stop and consider previous value

We add 2^1 to our answer. Looking back:

18  =  (2^1 * 5) + (something * 5) + rem
58 - (2^3 * 5) = (2^1 * 5) + (something * 5) + rem
58 =  (2^3 * 5) + (2^1 * 5) + (something * 5) + rem

You can notice we are gradually advancing towards equ II: Our new dividend is now:

18 - (2^1 * 5)  =  (something * 5) + rem
18 - (2 * 5) = something * 5 + rem
18 - 10 = something * 5 + rem
8 = something * 5 + rem

dividend = 8, divisor = 5 Repeating the process:

5 << 0 = 5           // less than dividend
5 << 1 = 5*2 = 10    // exceeds divided, so stop and consider previous value

We add 2^0 to our answer. New dividend:

8 = (2^0 * 5) + (something * 5) + rem
8 - 5 = something * 5 + rem
3 = something * 5 + rem

dividend = 3, divisor = 5 At this step, we stop iterating as our dividend is less than the divisor (we have also found our remainder = 3, as 5 should be multiplied with 0 and what remains is the remainder).

Looking back again for the last time:

3 = 0*5 + rem
8 = (2^0 * 5) + 3
18  =  (2^0 * 5) + (2^1 * 5) + 3
58 = (2^3 * 5) + (2^1 * 5) + (2^0 * 5) + 3

In the process, we have finally reached the equation we wanted to, and have got the answer as:

quotient = (2^3 + 2^1 + 2^0)

Code

Java

public int divide(int dividend, int divisor) {
	//handle special cases
	if (divisor == 0) return Integer.MAX_VALUE;
	if (divisor == -1 && dividend == Integer.MIN_VALUE)
		return Integer.MAX_VALUE;

	//get positive values
	long pDividend = Math.abs((long) dividend);
	long pDivisor = Math.abs((long) divisor);

	int ans = 0;
	while (pDividend >= pDivisor) {
		//calculate number of left shifts
		int numShift = 0;
		while (pDividend >= (pDivisor<< numShift)) {
			numShift++;
		}

		//dividend minus the largest shifted divisor
		ans += 1<< (numShift - 1);
		pDividend -= (pDivisor<< (numShift - 1));
	}

	if ((dividend > 0 && divisor > 0) || (dividend<0 && divisor<0)) {
		return ans;
	} else {
		return -ans;
	}
}

Complexity

⏰ Time complexity: O(log n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Using Binary Shifts#

Code#

Java#

Complexity#