# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
# Brute-force approach (O(n))
def divide(dividend, divisor):
    count = 0
    flag = 0
    if divisor < 0 and dividend < 0:
        divisor *= -1
        dividend *= -1
    elif dividend < 0:
        flag = 1
        dividend *= -1
    elif divisor < 0:
        flag = 1
        divisor *= -1
    if divisor == 1:
        count = dividend
    else:
        while dividend >= divisor:
            dividend -= divisor
            count += 1
    if flag:
        count *= -1
    if count > 2147483647:
        count = 2147483647
    elif count < -2147483648:
        count = -2147483648
    return count

print(divide(-2147483648, -15))


# +
# Optimized-approach (O(logn^2))
def divide(dividend, divisor):
    positive = (dividend >= 0) == (divisor >= 0)    # Positive if both signs are same
    INT_MAX = pow(2, 31) - 1
    dividend = abs(dividend)
    divisor = abs(divisor)
    res = 0
    while dividend >= divisor:
        multiply = 1    # 1 2 4 8 16
        rem_sum = divisor
        while (rem_sum + rem_sum) < dividend:
            multiply += multiply
            rem_sum += rem_sum
        res += multiply
        dividend -= rem_sum
    res = res if positive else -res
    return min(res, INT_MAX)

print(divide(16, 2))
# -



StarcoderdataJupyterScriptsDedupFiltered