29. Divide Two Integers – Leetcode Solutions

June 9, 2024

Table of Contents

Description:

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: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ - 1, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Examples:

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.

Solution in Python:

Python

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # Constants for 32-bit signed integer range
        MAX_INT = 2**31 - 1
        MIN_INT = -2**31
        
        # Handle edge case of overflow
        if dividend == MIN_INT and divisor == -1:
            return MAX_INT
        
        # Determine the sign of the result
        negative = (dividend < 0) != (divisor < 0)
        
        # Work with positive values for simplicity
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        # Initialize quotient
        quotient = 0
        
        # Bitwise approach to find the quotient
        while dividend >= divisor:
            temp_divisor = divisor
            multiple = 1
            # Double the divisor until it is less than the dividend
            while dividend >= (temp_divisor << 1):
                temp_divisor <<= 1
                multiple <<= 1
            # Subtract the largest found multiple of the divisor from the dividend
            dividend -= temp_divisor
            # Add the corresponding multiple to the quotient
            quotient += multiple
        
        # Apply the sign to the quotient
        if negative:
            quotient = -quotient
        
        # Ensure the result is within the 32-bit signed integer range
        return max(MIN_INT, min(MAX_INT, quotient))

# Example usage:
# sol = Solution()
# print(sol.divide(10, 3))  # Output: 3
# print(sol.divide(7, -3))  # Output: -2

Explanation:

Constants for 32-bit Signed Integer Range:
- MAX_INT and MIN_INT are defined to handle potential overflow cases.
Edge Case Handling:
- If dividend is MIN_INT and divisor is -1, the result would overflow, so return MAX_INT.
Sign Determination:
- The result should be negative if the signs of the dividend and divisor are different.
Convert to Positive Values:
- To simplify the computation, work with the absolute values of the dividend and divisor.
Bitwise Division:
- Initialize the quotient to 0.
- Use a bitwise approach to subtract the largest possible multiple of divisor from dividend until dividend is less than divisor.
- In each iteration, double the temp_divisor and multiple until temp_divisor exceeds dividend.
- Subtract temp_divisor from dividend and add multiple to quotient.
Sign Application:
- Apply the negative sign to the quotient if necessary.
Range Check:
- Ensure the result is within the 32-bit signed integer range.

This solution ensures that the division is performed without using multiplication, division, or the mod operator, and handles edge cases such as overflow and negative results correctly.

Solution in Javascript:

JavaScript

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    const INT_MAX = 2 ** 31 - 1;
    const INT_MIN = -(2 ** 31);

    // Edge case: division by zero
    if (divisor === 0) throw new Error("Divisor cannot be zero");

    // Edge case: overflow
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;

    // Determine the sign of the result
    const isNegative = (dividend < 0) !== (divisor < 0);

    // Work with absolute values
    let absDividend = Math.abs(dividend);
    let absDivisor = Math.abs(divisor);

    // Initialize the quotient
    let quotient = 0;

    // Perform the division using bitwise shifts
    while (absDividend >= absDivisor) {
        let temp = absDivisor;
        let multiple = 1;

        // Use exponential search to find the largest multiple
        while (absDividend >= (temp << 1) && (temp << 1) > 0) {
            temp <<= 1;
            multiple <<= 1;
        }

        // Subtract the largest found multiple from the dividend
        absDividend -= temp;
        quotient += multiple;
    }

    // Adjust the sign of the result
    if (isNegative) {
        quotient = -quotient;
    }

    // Clamp the result to the 32-bit signed integer range
    if (quotient < INT_MIN) return INT_MIN;
    if (quotient > INT_MAX) return INT_MAX;

    return quotient;
};

// Example usage:
console.log(divide(10, 3)); // Output: 3
console.log(divide(7, -3)); // Output: -2
console.log(divide(-2147483648, -1)); // Output: 2147483647
console.log(divide(2147483647, 1)); // Output: 2147483647
console.log(divide(1000000000, 1));

Solution in Java:

Java

class Solution {
    public int divide(int dividend, int divisor) {
        // Define constants for the 32-bit integer range
        final int INT_MAX = Integer.MAX_VALUE;
        final int INT_MIN = Integer.MIN_VALUE;
        
        // Handle edge cases
        if (divisor == 0) {
            throw new ArithmeticException("Divisor cannot be zero");
        }
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;  // Overflow case
        }

        // Determine the sign of the result
        boolean isNegative = (dividend < 0) != (divisor < 0);

        // Work with absolute values
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        // Initialize the quotient
        int quotient = 0;

        // Perform the division using bitwise shifts
        while (absDividend >= absDivisor) {
            long temp = absDivisor;
            long multiple = 1;

            // Use exponential search to find the largest multiple
            while (absDividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }

            // Subtract the largest found multiple from the dividend
            absDividend -= temp;
            quotient += multiple;
        }

        // Adjust the sign of the result
        if (isNegative) {
            quotient = -quotient;
        }

        // Return the result
        return quotient;
    }
}

// Example usage:
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.divide(10, 3));  // Output: 3
        System.out.println(solution.divide(7, -3)); // Output: -2
        System.out.println(solution.divide(-2147483648, -1)); // Output: 2147483647
        System.out.println(solution.divide(2147483647, 1)); // Output: 2147483647
        System.out.println(solution.divide(1000000000, 1)); // Output: 1000000000
    }
}

Solution in C#:

C#

public class Solution {
    public int Divide(int dividend, int divisor) {
        // Define constants for the 32-bit integer range
        const int INT_MAX = int.MaxValue;
        const int INT_MIN = int.MinValue;
        
        // Handle edge cases
        if (divisor == 0) {
            throw new DivideByZeroException("Divisor cannot be zero");
        }
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;  // Overflow case
        }

        // Determine the sign of the result
        bool isNegative = (dividend < 0) != (divisor < 0);

        // Work with absolute values
        long absDividend = Math.Abs((long) dividend);
        long absDivisor = Math.Abs((long) divisor);

        // Initialize the quotient
        int quotient = 0;

        // Perform the division using bitwise shifts
        while (absDividend >= absDivisor) {
            long temp = absDivisor;
            long multiple = 1;

            // Use exponential search to find the largest multiple
            while (absDividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }

            // Subtract the largest found multiple from the dividend
            absDividend -= temp;
            quotient += (int) multiple;
        }

        // Adjust the sign of the result
        if (isNegative) {
            quotient = -quotient;
        }

        // Return the result
        return quotient;
    }
}

29. Divide Two Integers – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

89. Gray Code – Leetcode Solutions

222. Count Complete Tree Nodes – Leetcode Solutions

Guide to Strings in Python: Functions and Methods

PEP 257: Python Docstring Conventions

Adding to a Dictionary in Python

209. Minimum Size Subarray Sum – Leetcode Solutions

263. Ugly Number – Leetcode Solutions

29. Divide Two Integers – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular