Divide Two Integers

Medium

TikTok

1 view

Topics:

Bit Manipulation

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³¹.

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³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Try coding it in LeetCode

Divide Two Integers

Medium

TikTok

1 view

Topics:

Bit Manipulation

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³¹.

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³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the dividend and divisor? Are they guaranteed to be 32-bit signed integers?
What should I return if the divisor is zero?
If the result of the division overflows the 32-bit signed integer range, what should I return?
Are both the dividend and divisor always integers, or could they be floating point numbers?
Can the dividend or divisor be negative, and if so, how should I handle the sign of the result?

Brute Force Solution

Approach

The problem asks us to find out how many times one number fits into another. The brute force approach is like repeatedly subtracting the smaller number from the larger number until we can't anymore, then counting how many subtractions we did.

Here's how the algorithm would work step-by-step:

First, figure out if either of the numbers are negative. Keep track of this information.
Make both numbers positive to make the subtraction easier.
Keep subtracting the smaller positive number from the larger positive number.
Each time you subtract, increase a counter by one.
Keep subtracting until the result of the subtraction is smaller than the number you were subtracting.
The final count is the answer, adjusted for the signs you noted earlier.
Also handle a couple of special cases like dividing by zero or really large numbers.

Code Implementation

def divide_two_integers(dividend, divisor):
    # Handle division by zero.
    if divisor == 0:
        return float('inf') if dividend > 0 else float('-inf')

    # Determine the sign of the result.
    negative_result = (dividend < 0) != (divisor < 0)

    # Convert both numbers to positive.
    positive_dividend = abs(dividend)
    positive_divisor = abs(divisor)

    quotient = 0
    while positive_dividend >= positive_divisor:
        # Repeatedly subtract divisor from dividend
        positive_dividend -= positive_divisor
        quotient += 1

    # Adjust the result based on the sign.
    if negative_result:
        quotient = -quotient

    # Handle integer overflow.
    max_int = 2**31 - 1
    min_int = -2**31
    if quotient > max_int:
        return max_int
    elif quotient < min_int:
        return min_int
    else:
        return quotient

Big(O) Analysis

Time Complexity

O(n) – The time complexity of the provided solution is O(n), where n represents the quotient of the division (i.e., dividend / divisor). The while loop iteratively subtracts the divisor from the dividend. In the worst case, the loop runs a number of times proportional to the quotient. Therefore, the number of subtractions, and thus the time complexity, is directly proportional to the quotient. This linear relationship gives a time complexity of O(n).

Space Complexity

O(1) – The described algorithm uses a few variables to store whether the input numbers are negative and a counter for the number of subtractions. The number of these variables remains constant regardless of the size of the input integers. Therefore, the auxiliary space required by this algorithm is constant.

Optimal Solution

Approach

The most efficient way to divide two numbers without using division, multiplication, or mod operations involves repeated subtraction but with a twist. Instead of subtracting the divisor one by one, we strategically subtract larger and larger powers of the divisor, getting closer to the final answer much faster.

Here's how the algorithm would work step-by-step:

First, handle the signs of the two numbers: note whether the final result should be positive or negative.
Work with the absolute values of the numbers to simplify the core logic.
Start with the largest possible power of two times the divisor that is still less than or equal to the dividend.
Subtract this value from the dividend and add the corresponding power of two to the quotient.
Repeat this process with smaller and smaller powers of two, until the dividend is smaller than the divisor.
Apply the sign from the beginning to the quotient.
Be careful to handle potential overflow issues when dealing with the minimum integer value.

Code Implementation

def divide_two_integers(dividend, divisor):
    # Handle the signs of the dividend and divisor.
    sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1

    dividend_abs = abs(dividend)
    divisor_abs = abs(divisor)

    quotient = 0
    # Subtract the divisor until dividend is smaller than divisor.
    while dividend_abs >= divisor_abs:
        temp_divisor = divisor_abs
        multiple = 1

        # Find the largest multiple of divisor that is <= dividend.
        while dividend_abs >= (temp_divisor << 1):
            if temp_divisor > (2**30):
                break
            temp_divisor <<= 1
            multiple <<= 1

        dividend_abs -= temp_divisor
        quotient += multiple

    # Apply the sign to the quotient.
    quotient *= sign

    # Handle integer overflow.
    min_int = -2**31
    max_int = 2**31 - 1
    if quotient > max_int:
        return max_int
    elif quotient < min_int:
        return min_int
    else:
        return quotient

Big(O) Analysis

Time Complexity

O(log n) – The algorithm repeatedly subtracts multiples of the divisor from the dividend, where the multiples are powers of two. In essence, it's finding the largest power of 2 (let's call it 'k') such that divisor * 2^k is less than or equal to dividend. It then subtracts divisor * 2^k and adds 2^k to the quotient. This process is repeated until the remaining dividend is less than the divisor. Since the dividend is effectively halved (in a power of 2 sense) at each step, the number of iterations is proportional to the logarithm (base 2) of the quotient's magnitude, not the dividend's magnitude. Thus, the time complexity is O(log n), where 'n' implicitly represents the magnitude of the resulting quotient.

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the sign, absolute values of the dividend and divisor, and the quotient. The steps outlined involve repeated subtraction and bitwise operations on these variables but do not introduce any auxiliary data structures that scale with the input. Therefore, the space required remains constant regardless of the input numbers. No lists, hash maps, or recursion stacks are utilized, resulting in O(1) auxiliary space complexity.

Edge Cases

Case	How to Handle
Divisor is zero	Handle division by zero by returning Integer.MAX_VALUE or throwing an exception based on problem specifications.
Dividend is zero	Return zero since any number divided into zero is zero.
Both dividend and divisor are Integer.MIN_VALUE	Handle this case to avoid potential overflow issues, return 1 based on problem definition if applicable, otherwise, handle appropriately.
Dividend is Integer.MIN_VALUE and divisor is -1	This leads to integer overflow, return Integer.MAX_VALUE.
Dividend is Integer.MAX_VALUE and divisor is 1	Return Integer.MAX_VALUE as the result.
Divisor is 1	Return the dividend as is because division by 1 yields the dividend.
Divisor is -1	Return the negation of the dividend, handling the Integer.MIN_VALUE overflow case separately.
Large dividend and divisor with a very small quotient	The iterative subtraction approach can be slow; use a bit-manipulation approach to optimize for speed.