algoadvance

Leetcode 29. Divide Two Integers

Problem Statement

Given two integers dividend and divisor, divide the two integers without using multiplication, division, or mod operators. Return the quotient after dividing the dividend by the divisor.

The integer division should truncate toward zero, meaning you discard the fractional part of the quotient.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both the dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than −2^31, then return −2^31.

Clarifying Questions

1. Q: What should happen if the quotient exceeds the 32-bit signed integer range?
   • A: Return 2^31 - 1 if it exceeds the positive range and -2^31 if it exceeds the negative range.
2. Q: How should I handle very large/small inputs?
   • A: You should check for overflow conditions explicitly and return the appropriate limits.

Strategy

1. Sign Determination: Determine the sign of the result based on the signs of the dividend and divisor.
2. Handle Edge Cases: Specifically handle the maximum negative value scenario, because -2^31 / -1 exceeds the positive 32-bit integer limit.
3. Binary Search Approach: Use a binary search approach by repeatedly doubling the divisor and subtracting it from the dividend until the dividend is smaller than the divisor.
4. Bitwise Manipulation: Use bitwise operations to perform the division faster.

Code

public class Solution {
    public int divide(int dividend, int divisor) {
        // Handle edge case where division overflow happens
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        
        // Determine the sign of the result
        boolean negative = (dividend < 0) ^ (divisor < 0);
        
        // Work with absolute values to handle negative numbers
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);
        
        int result = 0;
        
        while (absDividend >= absDivisor) {
            long temp = absDivisor, multiple = 1;
            while (absDividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            absDividend -= temp;
            result += multiple;
        }
        
        // Apply the sign
        return negative ? -result : result;
    }
}

Time Complexity

• Best Case: O(log n) where n is the quotient. This occurs because the algorithm doubles the divisor repeatedly, reducing the dividend logarithmically.
• Worst Case: O(log n) based on similar logic since each iteration reduces the problem space by about half.

This ensures an efficient solution, especially since we are avoiding costly operations like standard division and modulus directly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?