Divide two numbers without multiplication and division

Intuition:

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

Approach:

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.
Work with the absolute values of the dividend and the divisor to simplify the calculations.
Use a loop to repeatedly add the divisor to the sum until the sum does not become greater than the dividend.
Within the loop, increment the result storing the quotient and update the sum.
If the result exceeds the maximum or minimum values for an integer, clamp it to the respective limit, handling the overflow cases.
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.

Dry Run:

Solution:

#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;
}
class Solution {

    /* Function to divide two numbers
    without multiplication and division */
    public int divide(int dividend, int divisor) {

        // Base case
        if (dividend == divisor) return 1;

        // Variable to store the sign of result
        boolean 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 = Math.abs(dividend);
        int d = Math.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 > Integer.MAX_VALUE && isPositive)
            return Integer.MAX_VALUE;
        if (ans > Integer.MAX_VALUE && !isPositive)
            return Integer.MIN_VALUE;

        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1 * ans;
    }

    public static void main(String[] args) {
        int dividend = 10, divisor = 3;

        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();

        /* Function call to divide two numbers
        without multiplication and division */
        int ans = sol.divide(dividend, divisor);

        System.out.println("The result of dividing " + dividend + " and " + divisor + " is " + ans);
    }
}
class Solution:
    
    # Function to divide two numbers
    # without multiplication and division
    def divide(self, dividend, divisor):
        
        # Base case
        if dividend == divisor:
            return 1
        
        # Variable to store the sign of result
        isPositive = True
        
        # Updating the sign of quotient
        if dividend >= 0 and divisor < 0:
            isPositive = False
        elif dividend < 0 and divisor > 0:
            isPositive = False
            
        # Storing absolute dividend & divisor
        n = abs(dividend)
        d = abs(divisor)
        
        # Variable to store the answer and sum
        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 += 1
            # Update the sum
            sum += d
        
        # Handling overflowing condition
        if ans > 2**31 - 1 and isPositive:
            return 2**31 - 1
        if ans > 2**31 - 1 and not isPositive:
            return -2**31
        
        # Returning the quotient 
        # with proper sign
        return ans if isPositive else -1 * ans


if __name__ == "__main__":
    dividend = 10
    divisor = 3
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to divide two numbers
    # without multiplication and division
    ans = sol.divide(dividend, divisor)
    
    print(f"The result of dividing {dividend} and {divisor} is {ans}")
class Solution {
    
    /* Function to divide two numbers
    without multiplication and division */
    divide(dividend, divisor) {
        
        // Base case
        if (dividend === divisor) return 1;
        
        // Variable to store the sign of result
        let 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
        let n = Math.abs(dividend);
        let d = Math.abs(divisor);
        
        // Variable to store the answer and sum
        let 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 > Number.MAX_SAFE_INTEGER && isPositive) 
            return Number.MAX_SAFE_INTEGER;
        if (ans > Number.MAX_SAFE_INTEGER && !isPositive)
            return Number.MIN_SAFE_INTEGER;
        
        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1 * ans;
    }
}

const main = () => {
    let dividend = 10, divisor = 3;
    
    /* Creating an instance of 
    Solution class */
    let sol = new Solution();
    
    /* Function call to divide two numbers
    without multiplication and division */
    let ans = sol.divide(dividend, divisor);
    
    console.log(`The result of dividing ${dividend} and ${divisor} is ${ans}`);
};

main();

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.

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 2¹ + 2⁰.

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:

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.
Work with the absolute values of the dividend and the divisor to simplify the calculations.
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.
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.
If the result exceeds the maximum or minimum values for an integer, clamp it to the respective limit, handling the overflow cases
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.

Dry Run:

Solution:

#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;
}
class Solution {
    /* Function to divide two numbers
    without multiplication and division */
    public int divide(int dividend, int divisor) {
        
        // Base case
        if(dividend == divisor) return 1;
        
        // Variable to store the sign of result
        boolean 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 = Math.abs(dividend);
        int d = Math.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 > Integer.MAX_VALUE && isPositive) 
            return Integer.MAX_VALUE;
        if(ans > Integer.MAX_VALUE && !isPositive)
            return Integer.MIN_VALUE;
        
        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1*ans;
    }
    
    public static void main(String[] args) {
        int dividend = 10, divisor = 3;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to divide two numbers
        without multiplication and division */
        int ans = sol.divide(dividend, divisor);
        
        System.out.println("The result of dividing " + dividend + " and " + divisor + " is " + ans);
    }
}
class Solution:
    # Function to divide two numbers
    # without multiplication and division
    def divide(self, dividend, divisor):
        
        # Base case
        if dividend == divisor: return 1
        
        # Variable to store the sign of result
        isPositive = True
        
        # Updating the sign of quotient
        if dividend >= 0 and divisor < 0: 
            isPositive = False
        elif dividend < 0 and divisor > 0:
            isPositive = False
            
        # Storing absolute dividend & divisor
        n = abs(dividend)
        d = abs(divisor)
        
        # Variable to store the answer
        ans = 0
        
        # Looping while dividend is 
        # greater than equal to divisor
        while n >= d:
            count = 0
            
            # Finding the required 
            # largest power of 2
            while n >= (d << (count+1)):
                count += 1
            
            # Updating the answer & dividend
            ans += (1 << count)
            n -= d * (1 << count)
        
        # Handling overflowing condition
        if ans > 2**31 - 1 and isPositive: 
            return 2**31 - 1
        if ans > 2**31 - 1 and not isPositive:
            return -2**31
        
        # Returning the quotient 
        # with proper sign
        return ans if isPositive else -1 * ans

# Main function to test the solution
dividend = 10
divisor = 3

# Creating an instance of 
# Solution class
sol = Solution()

# Function call to divide two numbers
# without multiplication and division
ans = sol.divide(dividend, divisor)

print(f"The result of dividing {dividend} and {divisor} is {ans}")
class Solution {
    /* Function to divide two numbers
    without multiplication and division */
    divide(dividend, divisor) {
        
        // Base case
        if (dividend === divisor) return 1;
        
        // Variable to store the sign of result
        let 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
        let n = Math.abs(dividend);
        let d = Math.abs(divisor);
        
        // Variable to store the answer
        let ans = 0;
        
        /* Looping while dividend is 
        greater than equal to divisor */
        while (n >= d) {
            let 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 > 2147483647 && isPositive) 
            return 2147483647;
        if (ans > 2147483647 && !isPositive)
            return -2147483648;
        
        /* Returning the quotient 
        with proper sign */
        return isPositive ? ans : -1 * ans;
    }
}

// Main function to test the solution
const dividend = 10;
const divisor = 3;

/* Creating an instance of 
Solution class */
const sol = new Solution();

/* Function call to divide two numbers
without multiplication and division */
const ans = sol.divide(dividend, divisor);

console.log(`The result of dividing ${dividend} and ${divisor} is ${ans}`);

Complexity Analysis:

Time Complexity: O((logN)²) – (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.

Problem List

Divide two numbers without multiplication and division

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Edge Cases:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Edge Cases:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code