Introduction
Bit Manipulation and Binary Search are some of the few topics that students generally neglect while focusing on other important topics of Data Structures and Algorithms. However, when applied to questions, these topics enhance the time and space complexity of the problem and make the solution relatively easy and understandable.
Today we will discuss one such significant problem, Divide Two Integers that can easily be solved using Bitwise operators and binary search, and see how brute force may sometimes become inefficient and generate errors like Time Limit Exceed.
Problem Statement:
You have been given two integers, a dividend, and a divisor. The problem states that you have to divide two integers, the dividend, and divisor without using multiplication, division, or mod operator. Also, the function must return the floor value of the quotient.
Assumption→ We assume that we are dealing with an environment that can store integers only within the 32-bit signed integer range, i.e., [- 231, 231 - 1].
So assume that your function returns 231 - 1 when the division result overflows.
Example
1. DIVIDEND = 10
DIVISOR = 3
QUOTIENT = 10 / 3 = 3.333…. = 3 (Floor value)
2. DIVIDEND = 100
DIVISOR = -16
QUOTIENT = 100 / -16 = - 6.25 = -6 (Floor value)
3. DIVIDEND = -56
DIVISOR = -14
QUOTIENT = -56 / -14 = -4
4. DIVIDEND = -99
DIVISOR = 7
QUOTIENT = -99 / 7 = -14.1428… = -14 (Floor value)
Brute Force
Algorithm
- The question states that we cannot use the multiplication, division, or mod operator to divide two integers.
- So, we will make use of subtraction to find the answer.
- We will keep subtracting the divisor from the dividend and keep a count of the number of subtractions.
- This count is equal to the quotient of the two numbers.
- Also, we need to keep track of the sign of the dividend and the divisor.
Implementation:
Program:
- C
- C++
- Java
- Python
- Javascript
- C#
C
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
int divide(int dividend, int divisor) {
if (divisor == 1)
return dividend;
if (dividend == INT_MIN) {
dividend++;
}
int sign = -1, quotient = 0;
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
dividend = abs(dividend);
divisor = abs(divisor);
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return quotient * sign;
}
int main() {
int dividend, divisor;
printf("Enter the dividend and divisor: ");
scanf("%d %d", ÷nd, &divisor);
printf("The quotient is %d", divide(dividend, divisor));
return 0;
}
C++
// C++ program to divide two numbers using brute force.
#include <iostream>
#include <climits>
using namespace std;
// Function to find the quotient.
int divide(int dividend, int divisor)
{
if (divisor == 1)
return dividend;
if (dividend == INT_MIN)
{
dividend++;
}
// Initialising the sign as 1 and quotient as 0.
int sign = -1, quotient = 0;
// If one of the dividends or divisor is negative, the sign becomes negative.
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
// Taking positive values of both dividend and divisor.
dividend = abs(dividend);
divisor = abs(divisor);
// Calculating the value of quotient.
while (dividend >= divisor)
{
dividend -= divisor;
quotient++;
}
// Returning the answer by multiplying the sign with the quotient.
return quotient * sign;
}
int main()
{
int dividend, divisor;
// Taking user input.
cout << "Enter the dividend and divisor: ";
cin >> dividend >> divisor;
// Calling the function and printing the answer.
cout << "The quotient is " << divide(dividend, divisor);
return 0;
}Java
import java.util.Scanner;
public class Main {
public static int divide(int dividend, int divisor) {
if (divisor == 1)
return dividend;
if (dividend == Integer.MIN_VALUE) {
dividend++;
}
int sign = -1, quotient = 0;
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return quotient * sign;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the dividend and divisor: ");
int dividend = scanner.nextInt();
int divisor = scanner.nextInt();
System.out.println("The quotient is " + divide(dividend, divisor));
}
}
Python
def divide(dividend, divisor):
if divisor == 1:
return dividend
if dividend == -2147483648:
dividend += 1
sign, quotient = -1, 0
if (dividend < 0 and divisor < 0) or (dividend >= 0 and divisor >= 0):
sign = 1
dividend = abs(dividend)
divisor = abs(divisor)
while dividend >= divisor:
dividend -= divisor
quotient += 1
return quotient * sign
def main():
dividend, divisor = map(int, input("Enter the dividend and divisor: ").split())
print("The quotient is", divide(dividend, divisor))
if __name__ == "__main__":
main()
Javascript
function divide(dividend, divisor) {
if (divisor === 1)
return dividend;
if (dividend === -2147483648) {
dividend += 1;
}
let sign = -1, quotient = 0;
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return quotient * sign;
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question("Enter the dividend and divisor: ", (input) => {
const [dividend, divisor] = input.split(' ').map(Number);
console.log("The quotient is", divide(dividend, divisor));
rl.close();
});
}
main();
C#
using System;
class Program {
static int divide(int dividend, int divisor) {
if (divisor == 1)
return dividend;
if (dividend == int.MinValue) {
dividend++;
}
int sign = -1, quotient = 0;
if ((dividend < 0 && divisor < 0) || (dividend >= 0 && divisor >= 0))
sign = 1;
dividend = Math.Abs(dividend);
divisor = Math.Abs(divisor);
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return quotient * sign;
}
static void Main(string[] args) {
Console.Write("Enter the dividend and divisor: ");
string[] inputs = Console.ReadLine().Split(' ');
int dividend = int.Parse(inputs[0]);
int divisor = int.Parse(inputs[1]);
Console.WriteLine("The quotient is " + divide(dividend, divisor));
}
}
Input:
| Enter the dividend and divisor: -14 -2 |
Output:
| The quotient is 7. |
Time Complexity
The time complexity of this approach is O(abs(M - N) / N), where M is the dividend and N is the divisor.
The time complexity is linear since we traverse the numbers between M - N and divide them by N.
Space Complexity
The space complexity of this approach is O(1).
Since we are not using any extra space to store the numbers, the space complexity of this solution is constant, i.e. O(1).
NOTE→ Though this approach is correct, it will not be accepted as the problem’s solution because of the constraints. The IDE will always throw a Time Limit Exceed on test cases where the dividend is too large, and the divisor is too small.
Read More - Time Complexity of Sorting Algorithms, and Euclid GCD Algorithm
518+ registered 
