algoadvance

Leetcode 29. Divide Two Integers

Problem Statement

The problem requires you to divide two integers without using multiplication, division, and mod operator. The output should be the quotient after dividing the dividend by the divisor. The quotient should be truncated towards zero, which means it should remove the fractional part if any.

• Given two integers dividend and divisor, return the quotient after dividing dividend by divisor.
• Note: Assume we are dealing with the environment which 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, return 2^31 − 1, and if the quotient is strictly less than -2^31, return -2^31.

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:

• -2^31 <= dividend, divisor <= 2^31 - 1
• divisor != 0

Clarifying Questions

1. What should happen if the dividend is zero?
   • The result should be zero regardless of the divisor as long as the divisor is not zero, which is guaranteed by the constraints.
2. Negative and positive results?
   • The result should respect the sign rules of division (positive divided by positive or negative divided by negative is positive, otherwise, it’s negative).
3. Handling special cases like overflow?
   • The result should be clamped within the 32-bit signed integer range.

Strategy

1. Handling edge cases:
   • If divisor is 1 or -1, the result is dividend or -dividend respectively, accounting for overflow.
   • If dividend is zero, return zero.
2. Use bit manipulation and subtraction:
   • Use the method of repeated subtraction with bit manipulation to speed up the process.
   • Maintain a quotient and double the bits of the divisor until it surpasses the dividend.
   • Subtract the doubled value of the divisor from the dividend and increase the quotient accordingly.
3. Sign determination:
   • Determine if the result should be positive or negative.

Code

#include <iostream>
#include <climits>

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            // Handle overflow case
            return INT_MAX;
        }
        
        // Determine the sign of the result
        bool negative = (dividend > 0) ^ (divisor > 0);
        
        // Work with positive values
        long long absDividend = labs(dividend);
        long long absDivisor = labs(divisor);
        
        int quotient = 0;
        while (absDividend >= absDivisor) {
            long long temp = absDivisor, multiple = 1;
            while (absDividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            absDividend -= temp;
            quotient += multiple;
        }
        
        return negative ? -quotient : quotient;
    }
};

// Example Usage
int main() {
    Solution sol;
    std::cout << sol.divide(10, 3) << std::endl; // Output: 3
    std::cout << sol.divide(7, -3) << std::endl; // Output: -2
    return 0;
}

Time Complexity

The time complexity of this solution is (O(\log n)), where (n) is the absolute value of dividend. This logarithmic behaviour is due to doubling the divisor until it surpasses the dividend, reducing the dividend size logarithmically in each iteration.

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?