Задача: 29. Divide Two Integers
Сложность: medium

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора.

Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2.

Возвращает частное после деления делимого на делитель.

Примечание: Если частное строго больше 2³¹ - 1, верните 2³¹ - 1, а если частное строго меньше -2³¹, верните -2³¹.

Пример:

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

👨‍💻 Алгоритм:

1️⃣Определяем знак результата, исходя из знаков делимого и делителя.

2️⃣Работаем с абсолютными значениями, используя вычитание и суммирование.

3️⃣Реализуем алгоритм деления без использования / и *, возвращая результат в 32-битном диапазоне.

😎 Решение:

class Solution(object):  
    def divide(self, dividend, divisor):  
        if abs(divisor) == 1:  
            dividend = divisor * dividend  
            if dividend > 2**31 - 1:  
                return 2**31 - 1  
            if dividend < -2**31:  
                return -2**31  
            return dividend  

        quotient = 0  
        sign = -1 if (dividend < 0) ^ (divisor < 0) else 1  

        dividend, divisor = abs(dividend), abs(divisor)  
        while dividend >= divisor:  
            temp, multiple = divisor, 1  
            while dividend >= (temp << 1):  
                temp <<= 1  
                multiple <<= 1  
            dividend -= temp  
            quotient += multiple  

        return max(min(quotient * sign, 2**31 - 1), -2**31)

Ставь 👍 и забирай 📚 Базу знаний