This problem requires you to divide one integer by another without using multiplication, division, or mod operator. This is a popular DSA question at FAANG+ companies like Amazon and Microsoft. We have solved this problem using recursion and iteration.
Given two integers, find their quotient, i.e., the integer result of dividing the first integer by the second one.
{
"a": 5,
"b": 2
}
Output:
2
Constraints:
a, b <= 9 * 1015b != 0/) operator.*) operator.%) operator.Solution with time complexity O(a / b) and space complexity O(1) can be achieved using addition or subtraction.
We can divide our problem into four parts:
a >= 0 and b > 0a < 0 and b > 0a >= 0 and b < 0a < 0 and b < 0When a >= 0 and b > 0, we can do this:
sum = 0
q = 0
while (sum + b <= a)
sum += b
q++
return q
Some modification in the above code will also work with other combinations. But we can still improve the 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)
(231 * q31 + 230 * q30 + ... + 20 * 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 231 * b <= a, then we set q31 = 1. But if 231 * b > a, then we set q31 = 0.
When we set q31 = 0, we have to solve
(230 * q30 + ... + 20 * q0) * b = a\ˀ
and when we set q31 = 1, we have to solve
(230 * q30 + ... + 20 * q0) * b = a - 231 * 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 that follow are different implementations of the idea we discussed here.
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.
O(log(a)) due to the recursive function call.
O(log(a))
/*
* Asymptotic complexity in terms of \`a\`:
* Time: O(log(a)^2).
* Auxiliary space: O(log(a)).
* Total space: O(log(a)).
*/
long long divide(long long a, long long 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);
}
O(log(a)2).
O(1).
O(1).
/*
* Asymptotic complexity in terms of \`a\`:
* Time: O(log(a)^2).
* Auxiliary space: O(1).
* Total space: O(1).
*/
long long divide(long long a, long long 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 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;
}
After some observations in the iterative solution, we can notice that no_of_shifts always decreases. Suppose it decreases 60 -> 55 -> 50 -> ... -> 0, then 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++.
O(log(a) + log(a)) = O(log(a)).
O(1).
O(1).
/*
* Asymptotic complexity in terms of \`a\`:
* Time: O(log(a)).
* Auxiliary space: O(1).
* Total space: O(1).
*/
long long divide(long long a, long long 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 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;
}
We hope that these solutions to dividing an integer by another integer have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
