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