Given two integers one is a dividend and the other is the divisor, we need to find the quotient when the dividend is divided by the divisor without the use of any ” / “ and ” % “ operators.
Examples:
Input: dividend = 10, divisor = 2
Output: 5
Explanation: 10/2 = 5.Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333… which is truncated to 3.Input: dividend = 10, divisor = -2
Output: -5
Explanation: 10/-2 = -5.
Approach: To solve the problem using Binary Search follow the below idea:
We already know that Quotient * Divisor ? Dividend and the Quotient lie between 0 and Dividend. Therefore, we can assume the Quotient as mid, the Dividend as higher bound and 0 as the lower bound and can easily use binary search to satisfy the terms of division which is Quotient * Divisor ? Dividend.
Follow the steps to solve the problem:
- At first, set high = dividend and low = 0 .
- Then, we need to find the mid ( i.e Quotient ) = low + (high – low ) / 2 .
- Then, we perform Binary Search in the range of 0 to the dividend.
- If mid * divisor > dividend, then update high = mid – 1 .
- Else we update low = mid + 1
- The value of mid which satisfies the condition (i.e mid * divisor ? dividend) is our Quotient.
- Then, we return it by checking the Parity.
Below is the implementation of the above approach:
C++
// C++ code to find the Quotient// using Binary Search Algorithm.#include <bits/stdc++.h>using namespace std;// Function to find the quotient using binary searchint divide_binary_search(int dividend, int divisor){ if (divisor == 1) return dividend; if (divisor == -1) return -dividend; // Declaring and Initialising // the variables. long long low = 0, high = abs(dividend), mid; // To store the Quotient. int quotient = 0; while (low <= high) { // Calculating mid. mid = low + (high - low) / 2; // To search in lower bound. if (abs(mid * divisor) > abs(dividend)) high = mid - 1; // To search in upper bound. else { quotient = mid; low = mid + 1; } } // Checking the parity and // returning the Quotient. if ((dividend < 0 && divisor < 0 || dividend > 0 && divisor > 0)) return quotient; else return -quotient;}// Driver Codeint main(){ int dividend = 10, divisor = 2; // Function call cout << "The Quotient is : " << divide_binary_search(dividend, divisor); return 0;} |
Java
// Java code to find the Quotient// using Binary Search Algorithm.import java.io.*;class GFG { // Function to find the quotient using binary search public static long divide_binary_search(int dividend, int divisor) { if (divisor == 1) return dividend; if (divisor == -1) return -dividend; // If the dividend is-2147483648 and // the divisor is -1, then // -2147483648 / -1 = 2147483648 since, // both "-"ve cancel each other and // return INT_MAX. else if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; // Declaring and Initialising // the variables. long low = 0, high = Math.abs(dividend), mid = 0; // To store the Quotient. long quotient = 0; while (low <= high) { // Calculating mid. mid = low + (high - low) / 2; // To search in lower bound. if (Math.abs(mid * divisor) > Math.abs(dividend)) high = mid - 1; // To search in upper bound. else { quotient = mid; low = mid + 1; } } // Checking the parity and // returning the Quotient. if ((dividend < 0 && divisor < 0 || dividend > 0 && divisor > 0)) return quotient; else return -quotient; } // Driver Code public static void main(String[] args) { int dividend = 10, divisor = 2; // Function call System.out.print( "The Quotient is : " + divide_binary_search(dividend, divisor)); }}// This code is contributed by Rohit Pradhan |
Python3
# python code to find the Quotient# using Binary Search Algorithm.import math# Function to find the quotient using binary searchdef divide_binary_search(dividend, divisor): if (divisor == 1): return dividend if (divisor == -1): return -dividend # Declaring and Initialising # the variables. low = 0 high = abs(dividend) mid = 0 # To store the Quotient. quotient = 0 while (low <= high): # Calculating mid. mid = low + math.floor((high - low) / 2) # To search in lower bound. if (abs(mid * divisor) > abs(dividend)): high = mid - 1 # To search in upper bound. else: quotient = mid low = mid + 1 # Checking the parity and # returning the Quotient. if ((dividend < 0 and divisor < 0 or dividend > 0 and divisor > 0)): return quotient else: return -quotient# Driver Codedividend = 10divisor = 2# Function callprint("The Quotient is :", divide_binary_search(dividend, divisor))# This code is contributed by ksam24000 |
C#
// C# implementationusing System;public class GFG { // Function to find the quotient using binary search public static int divide_binary_search(int dividend, int divisor) { if (divisor == 1) return dividend; if (divisor == -1) return -dividend; // Declaring and Initialising // the variables. long low = 0, high = Math.Abs(dividend); long mid; // To store the Quotient. int quotient = 0; while (low <= high) { // Calculating mid. mid = low + ((high - low) / 2); // To search in lower bound. if (Math.Abs(mid * divisor) > Math.Abs(dividend)) high = mid - 1; // To search in upper bound. else { quotient = (int)mid; low = mid + 1; } } // Checking the parity and // returning the Quotient. if ((dividend < 0 && divisor < 0 || dividend > 0 && divisor > 0)) return quotient; else return -quotient; } static public void Main() { int dividend = 10, divisor = 2; // Function call Console.WriteLine( "The Quotient is : " + divide_binary_search(dividend, divisor)); }}// this code is contributed by ksam24000 |
Javascript
// JavaScript code for the above approach// Function to find the quotient using binary searchfunction divide_binary_search(dividend, divisor){ if (divisor == 1) return dividend; if (divisor == -1) return -dividend; // Declaring and Initialising // the variables. let low = 0, high = Math.abs(dividend), mid; // To store the Quotient. let quotient = 0; while (low <= high) { // Calculating mid. mid = low + (high - low) / 2; // To search in lower bound. if (Math.abs(mid * divisor) > Math.abs(dividend)) high = mid - 1; // To search in upper bound. else { quotient = mid; low = mid + 1; } } // Checking the parity and // returning the Quotient. if ((dividend < 0 && divisor < 0 || dividend > 0 && divisor > 0)) return quotient; else return -quotient;}// Driver Codelet dividend = 10, divisor = 2;// Function callconsole.log("The Quotient is : " + divide_binary_search(dividend, divisor));// This code is contributed by Potta Lokesh |
Output
The Quotient is : 5
Time Complexity: O(log N), as Binary Search algorithm is used.
Auxiliary Space: O(1), since no extra space has been used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
