Divide An Integer By Another Integer Problem

Given two integers, find their quotient, i.e. the integer result of dividing the first by the second.

Example

Input: 5, 2

Output: 2

‍

Notes

Input Parameters: Two integers a and b.

Output: An integer quotient of a and b.

Constraints:

● -10^18

● b != 0

● You are not allowed to use division (/) operator.

● You are not allowed to use multiplication (*) operator.

● You are not allowed to use mod (%) operator.

‍

Solution

Solution with time complexity O(a / b) and space complexity O(1) can be achieved using addition or subtraction.

We can divide our problem in four parts:

1) a >= 0 and b > 0

2) a < 0 and b > 0

3) a >= 0 and b < 0

4) a < 0 and b < 0

When a >= 0 and b > 0 then we can do something like this:

sum = 0

q = 0

while (sum + b

sum += b

q++

return q

Some modification in the above code will also work with other combinations. But still we can improve time complexity.

Let's take a and b such that a % b = 0 so we can write q = a / b. q * b = a. Let’s think about the binary representation of the numbers.

q * b = q

(q31q30...q0) * b = a (in the binary representation)

(2^31 * q31 + 2^30 * q30 + ... + 2^0 * q0) * b = a

To find the value for each bit we can start from the left side.

First we try to set q31 = 1, if 2^31 * b <= a="" then="" we="" set="" q31="1," but="" if="" 2^31="" *="" b=""> a then we set q31 = 0. </=>

When we set q31 = 0 then we have to solve

(2^30 * q30 + ... + 2^0 * q0) * b = a

and when we set q31 = 1 then we have to solve

(2^30 * q30 + ... + 2^0 * q0) * b = a - 2^31 * b.

Consider 37 / 3. We keep on shifting the divisor by 1 binary position (that multiplies it by 2) until it exceeds 37. Here it will be 3 -> 6 -> 12 -> 24. Now we can write our division 37 / 3 = (37 / (3 * 8)) * 8 + (37 - (3 * 8)) / 3. Now first part is (37 / 24) * 8 = 1 * 8 = 1 * 2^(number of shifts). Second part is 13 / 3 and it is a smaller version of the original problem.

All three solutions we provided are different implementations of the idea we discussed here.

‍

1) other_solution1.cpp: Recursive solution.

Time Complexity:

O(log(a) ^ 2). Recursive function can be called O(log(a)) times, and in each function call we are shifting no_of_shifts times that is O(log(a)). Shift operation takes O(1) time.

Auxiliary Space Used:

O(log(a)) due to the recursive function call.

Space Complexity:

O(log(a))

// -------- START --------

long long int divide(long long int a, long long int b)
{
	// 0 / non_zero = 0
	if (a == 0)											
	{
		return 0;
	}
	// neg / pos or pos / neg
	if ((a < 0 && b > 0) || (a > 0 && b < 0))			
	{
		return -divide(abs(a), abs(b));
	}
	// neg / neg
	if (a < 0 && b < 0)									
	{
		return divide(-a, -b);
	}
	// like 2 / 5
	if (a < b)											
	{
		return 0;
	}
	// 37 / 3 can be written as 8 * (37 / (3 * 8)) + (37 - (3 * 8)) / 3
	int no_of_shifts = 0;
	while ((b << (no_of_shifts + 1)) <= a)
	{
		no_of_shifts++;
	}
	return (1LL << no_of_shifts) + divide(a - (b << no_of_shifts), b);
}

// -------- END --------

2) other_solution2.cpp: Iterative solution.

Time Complexity:

O(log(a)^2).

Auxiliary Space Used:

O(1).

Space Complexity:

O(1).

// -------- START --------

long long int divide(long long int a, long long int b)
{
	// 0 / non_zero = 0
	if (a == 0)											
	{
		return 0;
	}
	// neg / pos or pos / neg
	if ((a < 0 && b > 0) || (a > 0 && b < 0))			
	{
		return -divide(abs(a), abs(b));
	}
	// neg / neg
	if (a < 0 && b < 0)									
	{
		a = -a;
		b = -b;
	}
	long long int ans = 0;
	while(a >= b)
	{
		int no_of_shifts = 0;
		while ((b << (no_of_shifts + 1)) <= a)
		{
			no_of_shifts++;
		}
		ans += (1LL << no_of_shifts);
		a -= (b << no_of_shifts);
	}
	return ans;
}

// -------- END --------

3) optimal_solution.cpp: Iterative solution.

After some observations in other_solution2.cpp we can notice that no_of_shifts always decreases. Suppose it decreases 60 -> 55 -> 50 -> ... -> 0. Then in other_solution2.cpp we start no_of_shifts from 0 and increment it to 60, again for 55 we will increment no_of_shifts from 0 to 55. But as we know it will decrease from 60 to 55, we can directly start from 60 and quickly reach 55. Then from 55 to 50 (instead of 0 to 55)... After this optimization, O(log(a)) shifts remain. Shift operation takes O(1) time.

If you use C, replace abs() calls by fabs() after copying our solution in C++.

Time Complexity:

O(log(a) + log(a)) = O(log(a)).

Auxiliary Space Used:

O(1).

Space Complexity:

O(1).

// -------- START --------

long long int divide(long long int a, long long int b)
{
	// 0 / non_zero = 0
	if (a == 0)											
	{
		return 0;
	}
	// neg / pos or pos / neg
	if ((a < 0 && b > 0) || (a > 0 && b < 0))			
	{
		return -divide(abs(a), abs(b));
	}
	// neg / neg
	if (a < 0 && b < 0)									
	{
		a = -a;
		b = -b;
	}
	long long int ans = 0;
	int no_of_shifts = 0;
	while ((b << (no_of_shifts + 1)) <= a)
	{
		no_of_shifts++;
	}
	while(a >= b)
	{
		while ((b << no_of_shifts) > a)
		{
			no_of_shifts--;
		}
		ans += (1LL << no_of_shifts);
		a -= (b << no_of_shifts);
	}
	return ans;
}

// -------- END --------