Divide two quantity utilizing Binary search with out utilizing any / and % operator

[ad_1]

View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

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 using 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 unravel the issue utilizing Binary Search observe the under concept:

We already know that Quotient * Divisor ≤ Dividend and the Quotient lie between 0 and Dividend. Due to this fact, we will assume the Quotient  as mid, the Dividend as larger certain and 0 because the decrease certain and might 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. 

Beneath is the implementation of the above strategy:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int divide_binary_search(int dividend, int divisor)

{

    

    if (dividend == divisor)

        return 1;

  

    

    

    

    if (dividend == INT_MIN && divisor == 1)

        return INT_MIN;

  

    

    

    

    

    

    else if (dividend == INT_MIN && divisor == -1)

        return INT_MAX;

  

    

    

    lengthy lengthy low = 0, excessive = abs(dividend), mid;

  

    

    int quotient = 0;

  

    whereas (low <= excessive) {

  

        

        mid = low + (excessive - low) / 2;

  

        

        if (abs(mid * divisor) > abs(dividend))

            excessive = mid - 1;

  

        

        else {

            quotient = mid;

            low = mid + 1;

        }

    }

  

    

    

    if ((dividend < 0 && divisor < 0

         || dividend > 0 && divisor > 0))

        return quotient;

    else

        return -quotient;

}

  

int important()

{

    int dividend = 10, divisor = 2;

  

    

    cout << "The Quotient is : "

         << divide_binary_search(dividend, divisor);

  

    return 0;

}

Output

The Quotient is : 5

Time Complexity: O(log N), as Binary Search algorithm is used.
Auxiliary Area: O(1), since no additional area has been used.

[ad_2]

Leave a Reply