This a problem i came across while practicing binary search. Here is the problem:
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
A Brute force Solution is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error.
How to solve the problem efficiently or using Binary Search ??
Also provide the time complexity as well.