[Solved] Divide Two Integers-29 C++, Java, Python -Microsoft,Google, Amazon, Media.net

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

Solution

Intuition

Since * / % aren’t allowed in the description, what if other things like arrays, long, Math.abs, bit manipulation, etc. weren’t allowed either?

Approach

This version only uses + – and logic. The program uses negative absolute values because many of the test cases involve -2147483648. Using negative absolute values means the only case that can’t be handled is in the first line.

Complexity

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

class Solution {
public:
    int divide(int dividend, int divisor) {
	    if (dividend == -2147483648 && divisor == -1) return 2147483647; // the only case that will generate an invalid result
        
		bool negative = false; // determine if the result is negative
        if (dividend < 0) negative = true; // if dividend is negative set negative to true
        else dividend = 0 - dividend; // get negative absolute value
        if (divisor < 0) negative = !negative; // if divisor is negative toggle negative
        else divisor = 0 - divisor; // get negative absolute value
        
		int quotient = 0; // value to store the result
        while (dividend <= divisor) { // both values are negative dividend will increase toward 0
            int count = -1; // value to update the result
            int start = divisor; // value to update the dividend
            while (start > -2147483648 - start && start + start > dividend) { // while doubling the value doesn't exceed constraints
                start += start; // double the value to update the dividend
                count += count; // double the value to update the result
            }
            dividend -= start; // update the dividend
            quotient += count; // update the result
        }
        
		if (negative) return quotient; // result is already negative
        return 0 - quotient; // update result to positive
    }
};

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == -2147483648 && divisor == -1) return 2147483647; // the only case that will generate an invalid result
       
	    boolean negative = false; // determine if the result is negative
        if (dividend < 0) negative = true; // if dividend is negative set negative to true
        else dividend = 0 - dividend; // get negative absolute value
        if (divisor < 0) negative = !negative; // if divisor is negative toggle negative
        else divisor = 0 - divisor; // get negative absolute value
       
	    int quotient = 0; // value to store the result
        while (dividend <= divisor) { // both values are negative dividend will increase toward 0
            int count = -1; // value to update the result
            int start = divisor; // value to update the dividend
            while (start > -2147483648 - start && start + start > dividend) { // while doubling the value doesn't exceed constraints
                start += start; // double the value to update the dividend
                count += count; // double the value to update the result
            }
            dividend -= start; // update the dividend
            quotient += count; // update the result
        }
       
	   if (negative) return quotient; // result is already negative
       return 0 - quotient; // update result to positive
    }
}

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if (dividend == -2147483648 and divisor == -1):
            return 2147483647
        negative = False
        if (dividend < 0):
            negative = True
        else:
            dividend = 0 - dividend
        if (divisor < 0):
            negative = not negative
        else:
            divisor = 0 - divisor
        quotient = 0;
        while (dividend <= divisor):
            count = -1
            start = divisor
            while (start > -2147483648 - start and start + start > dividend):
                start = start + start
                count = count + count
            dividend = dividend - start
            quotient = quotient + count
        if (negative):
            return quotient
        return 0 - quotient

Happy Learning – If you require any further information, feel free to contact me.