About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

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 --------

Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts