Divide without Division, Multiplication & Mod Editorial

Practice Problem Link: Divide without Division, Multiplication & Mod

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given two integers, a and b. Return the quotient after dividing a by b.
You cannot use the multiplication, division or modulo operator.

Naive Approach

The naive idea relies on the fact that division is just repeated subtraction. So, we can count the number of times we can subtract the first number from the second number and that will be our quotient, using which we calculate the result.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int divide(int a, int b) {
    int sign = 1;
	if((a > 0 && b < 0) || (a < 0 && b > 0)) {
		sign = - 1;
	}
	a = abs(a);
	b = abs(b);
	int quotient = 0;
	while(a >= b) {
		a -= b;
		quotient++;
	}
	return sign * quotient;
}

Java

class Solution {
    int divide(int a, int b) {
        int sign = 1;
		if((a > 0 && b < 0) || (a < 0 && b > 0)) {
			sign = - 1;
		}
		a = Math.abs(a);
		b = Math.abs(b);
		int quotient = 0;
		while(a >= b) {
			a -= b;
			quotient++;
		}
		return sign * quotient;
    }
}

Optimal Approach

The optimal approach relies on using bitwise operators to solve this problem efficiently. We will try to represent the quotient in binary to utilize the bitwise operators efficiently. The algorithm is:

• Find the MSB in the quotient.
• We will now search for the first bit such that divisor / 2i  < dividend , and then for that ith bit we will update it when we find it.
• If the above condition is true, then subtract divisor / 2i from dividend.Then add 2ⁱ to the quotient. 
• Compute the sign of the result using signs of the given numbers.
• Return the calculated quotient along with the appropriate sign

 Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Implementation

C++

int divide(int a, int b) {
    int sign = 1;
	if((a > 0 && b < 0) || (a < 0 && b > 0)) {
		sign = - 1;
	}
	a = abs(a);
	b = abs(b);
    int quotient = 0;
	for (int i = 30; i >= 0; i--) {
		long long temp = (long long)b << (long long)i;
		if(temp <= a) {
			a -= temp;
			quotient += 1 << i;
		}
	}
	return sign * quotient;
}

Java

class Solution {
    int divide(int a, int b) {
        int sign = 1;
		if((a > 0 && b < 0) || (a < 0 && b > 0)) {
			sign = - 1;
		}
		a = Math.abs(a);
		b = Math.abs(b);
		int quotient = 0;
		for (int i = 30; i >= 0; i--) {
			long temp = (long)b << (long)i;
			if(temp <= a) {
				a -= temp;
				quotient += 1 << i;
			}
		}
		return sign * quotient;
    }
}