Problem Statement

Given the two integers, dividend and divisor. Divide without using the mod, division, or multiplication operators and return the quotient.

The fractional portion of the integer division should be lost as it truncates toward zero.

As an illustration, 8.345 and -2.7335 would be reduced to 8 and -2 respectively.

Examples

Example 1:

Input: Dividend = 10, Divisor = 3
Output: 3

Explanation: 10/3 = 3.33, truncated to 3.

Example 2:

Input: Dividend = 7, Divisor = -3
Output: -2

Explanation: 7/-3 = -2.33, truncated to -2.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The brute force way to solve this problem is to repeatedly add the divisor until the sum is smaller than the dividend.

Approach:

1. Check the signs of the dividend and the divisor to determine if the result should be positive or negative. If one is positive and the other is negative, the result is negative. Otherwise, it is positive.
2. Work with the absolute values of the dividend and the divisor to simplify the calculations.
3. Use a loop to repeatedly add the divisor to the sum until the sum does not become greater than the dividend.
4. Within the loop, increment the result storing the quotient and update the sum.
5. If the result exceeds the maximum or minimum values for an integer, clamp it to the respective limit, handling the overflow cases.
6. Adjust the sign of the result based on the initial sign determination and return it.

Edge Cases:

What if the divisor and dividend are identical?
To save the computation, directly 1 can be returned.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to divide two numbers
    without multiplication and division */
    int divide(int dividend, int divisor) {
        
        // Base case
        if(dividend == divisor) return 1;
        
        // Variable to store the sign of result
        bool isPositive = true;
        
        // Updating the sign of quotient
        if(dividend >= 0 && divisor < 0) 
            isPositive = false;
        else if(dividend < 0 && divisor > 0)
            isPositive = false;
            
        // Storing absolute dividend & divisor
        int n = abs(dividend);
        int d = abs(divisor);
        
        // Variable to store the answer and sum
        int ans = 0, sum = 0;
        
        /* Looping while sum added to divisor is
        less than or equal to divisor */
        while(sum + d <= n) {
            
            // Increment the count
           ans++;
           // Update the sum
           sum += d;
        }
        
        // Handling overflowing condition
        if(ans > INT_MAX && isPositive) 
            return INT_MAX;
        if(ans > INT_MAX && !isPositive)
            return INT_MIN;
        
        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1*ans;
    }
};

int main() {
    int dividend = 10, divisor = 3;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to divide two numbers
    without multiplication and division */
    int ans = sol.divide(dividend, divisor);
    
    cout << "The result of dividing " << dividend << " and " << divisor << " is " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(dividend)
  • In the worst case when the divisor is 1, the number of iterations taken will be O(dividend).
• Space Complexity: O(1) Using a couple of variables i.e., constant space.

2️⃣ Optimal Approach (Bit Manipulation)

Intuition:

The key idea is to repeatedly subtract the divisor from the dividend until the dividend is smaller than the divisor. However, doing this one step at a time can be very slow, so we use a method that speeds up the process by leveraging bit manipulation.

An important concept to know is that the quotient can be expressed as the sum of powers of 2.

Example: Dividend = 10, Divisor = 3.

Quotient = 10/3 = 3 which can be represented as 21 + 20.

Now, instead of subtracting the divisor from the dividend one unit at a time, we use powers of 2 (using bit shifting) to subtract larger multiples of the divisors in each step. This makes the process faster.

Approach:

1. Check the signs of the dividend and the divisor to determine if the result should be positive or negative. If one is positive and the other is negative, the result is negative. Otherwise, it is positive.
2. Work with the absolute values of the dividend and the divisor to simplify the calculations.
3. Use a loop to repeatedly subtract the divisor from the dividend. Instead of subtracting the divisor one at a time, shift the divisor left (equivalent to multiplying by powers of 2) to subtract larger chunks, making the process faster.
4. Within the loop, find the maximum power of two such that the shifted divisor is still less than or equal to the remaining part of the dividend. Subtract this value from the dividend and add the corresponding power of two to the result.
5. If the result exceeds the maximum or minimum values for an integer, clamp it to the respective limit, handling the overflow cases
6. Adjust the sign of the result based on the initial sign determination and return it.

Edge Cases:

What if the divisor and dividend are identical?
To save the computation, directly 1 can be returned.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to divide two numbers
    without multiplication and division */
    int divide(int dividend, int divisor) {
        
        // Base case
        if(dividend == divisor) return 1;
        
        // Variable to store the sign of result
        bool isPositive = true;
        
        // Updating the sign of quotient
        if(dividend >= 0 && divisor < 0) 
            isPositive = false;
        else if(dividend < 0 && divisor > 0)
            isPositive = false;
            
        // Storing absolute dividend & divisor
        int n = abs(dividend);
        int d = abs(divisor);
        
        // Variable to store the answer
        int ans = 0;
        
        /* Looping while dividend is 
        greater than equal to divisor */
        while(n >= d) {
            int count = 0;
            
            /* Finding the required 
            largest power of 2 */
            while(n >= (d << (count+1))) {
                count++;
            }
            
            // Updating the answer & dividend
            ans += (1 << count);
            n -= d*(1 << count);
        }
        
        // Handling overflowing condition
        if(ans > INT_MAX && isPositive) 
            return INT_MAX;
        if(ans > INT_MAX && !isPositive)
            return INT_MIN;
        
        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1*ans;
    }
};

int main() {
    int dividend = 10, divisor = 3;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to divide two numbers
    without multiplication and division */
    int ans = sol.divide(dividend, divisor);
    
    cout << "The result of dividing " << dividend << " and " << divisor << " is " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O((logN)^2) – (where N is the absolute value of dividend)
  • The outer loop runs for O(logN) times.
  • The inner loop runs for O(logN) (approx.) times as well.
• Space Complexity: O(1) – Using a couple of variables i.e., constant space.