Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid First Name
*Invalid Last Name
*Invalid Phone Number
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

# Divide An Integer By Another Integer Problem

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.

# Divide An Integer By Another Integer Problem Statement

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

## Example

``````{
"a": 5,
"b": 2
}
``````

Output:

``````2
``````

## Notes

Constraints:

• -9 * 1015 <= `a`, `b` <= 9 * 1015
• `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:

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`, 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.

# Divide An Integer By Another Integer Solution 1: Recursive

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

O(log(a))

## Code For Divide An Integer By Another Integer Solution 1: Recursive

``````/*
* 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);
}

``````

# Divide An Integer By Another Integer Solution 2: Iterative

O(log(a)2).

O(1).

O(1).

## Code For Divide An Integer By Another Integer Solution 2: Iterative

``````/*
* 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;
}

``````

# Divide An Integer By Another Integer Solution 3: Optimal

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

## Time Complexity

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

O(1).

O(1).

## Code For Divide An Integer By Another Integer Solution 3: Optimal

``````/*
* 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: