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

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

**Time Complexity:**

O(log(a)^2).

**Auxiliary Space Used:**

O(1).

**Space Complexity:**

O(1).

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