Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

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:

- -9 * 10
^{15}<=`a`

,`b`

<= 9 * 10^{15} `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 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 > 0`

`a < 0`

and`b > 0`

`a >= 0`

and`b < 0`

`a < 0`

and`b < 0`

When `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)

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

, we have to solve

(2^{30} * `q30`

+ ... + 2^{0} * `q0`

) * `b`

= `a`

\ˀ
and when we set `q31 = 1`

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

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.