Divide Two Integers

Sources: leetcode 29

Rating: medium

Given two integers dividend and divisor, divide two integers without using multiplication, division, or modulus operators. Return the quotient. Note that integer division truncates, and that 32-bit integers have maximum and minimum values.

def divide(dividend: int, divisor: int) -> int:
    # return the quotient without using multiplication, division, or modulus

Solution

First, check if the output quotient would be negative to simplify the later math.

def divide(dividend, divisor):
    negative = (dividend < 0) != (divisor < 0)
    divisor, dividend = abs(divisor), abs(dividend)
    # return the quotient

Since multiplication and division operators are forbidden, addition and subtraction will have to be used instead. To that end, start with a quotient value and a count value that will be used to build up to the final result while dividend is subtracted down using divisor.

def divide(dividend, divisor):
    negative = (dividend < 0) != (divisor < 0)
    divisor, dividend = abs(divisor), abs(dividend)
    quotient = 0
    count = 1
    # calculate the quotient using count
    return quotient

The reason count is used is because a linear approach of simply adding up divisor values would be too slow. Using count allows skipping up in multiples instead of iterating one by one. However, this creates the possibility of skipping too far, in which case the original divisor value should be remembered for resets.

def divide(dividend, divisor):
    negative = (dividend < 0) != (divisor < 0)
    divisor, dividend = abs(divisor), abs(dividend)
    quotient = 0
    count = 1
    div = divisor
    while div <= dividend:
        dividend -= div
        quotient += count
        count += count
        div += div
        # ensure dividend and divisor do not cross one another
    return quotient

This creates the possibility of div and dividend crossing one another, in which case the last step needs to be reverted back down by resetting the div and count values.

def divide(dividend, divisor):
    negative = (dividend < 0) != (divisor < 0)
    divisor, dividend = abs(divisor), abs(dividend)
    quotient = 0
    count = 1
    div = divisor
    while div <= dividend:
        dividend -= div
        quotient += count
        count += count
        div += div
        if dividend < div:
            div = divisor
            count = 1
    return quotient

However, as 32 bit integers are limited in value, the returned quotient must be bound in value.

Final Code

def divide(dividend, divisor):
    negative = (dividend < 0) != (divisor < 0)
    divisor, dividend = abs(divisor), abs(dividend)
    quotient = 0
    count = 1
    div = divisor
    while div <= dividend:
        dividend -= div
        quotient += count
        count += count
        div += div
        if dividend < div:
            div = divisor
            count = 1
    if negative:
        return max(-2147483648, -quotient)
    else:
        return min(quotient, 2147483647)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s