Given two integers one is a dividend and the opposite is the divisor, we have to discover the quotient when the dividend is split by the divisor with out the usage of any ” / “ and ” % “ operators.
Examples:
Enter: dividend = 10, divisor = 2
Output: 5
Rationalization: 10/2 = 5.Enter: dividend = 10, divisor = 3
Output: 3
Rationalization: 10/3 = 3.33333… which is truncated to three.Enter: dividend = 10, divisor = -2
Output: -5
Rationalization: 10/-2 = -5.
Method: To resolve the issue utilizing Binary Search observe the beneath concept:
We already know that Quotient * Divisor ≤ Dividend and the Quotient lie between 0 and Dividend. Subsequently, we will assume the Quotient as mid, the Dividend as greater sure and 0 because the decrease sure and may simply use binary search to fulfill the phrases of division which is Quotient * Divisor ≤ Dividend.
Comply with the steps to resolve the issue:
- At first, set excessive = dividend and low = 0 .
- Then, we have to discover the mid ( i.e Quotient ) = low + (excessive – low ) / 2 .
- Then, we carry out Binary Search within the vary of 0 to the dividend.
- If mid * divisor > dividend, then replace excessive = mid – 1 .
- Else we replace low = mid + 1
- The worth of mid which satisfies the situation (i.e mid * divisor ≤ dividend) is our Quotient.
- Then, we return it by checking the Parity.
Under is the implementation of the above strategy:
C++
|
|
The Quotient is : 5
Time Complexity: O(log N), as Binary Search algorithm is used.
Auxiliary Area: O(1), since no further area has been used.
