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

Даны два целых числа dividend и divisor.
Выполните деление без использования операторов *, /, %.
Результат должен быть усечён до целого и находиться в пределах 32-битного целого числа.

Пример:

Input: dividend = 10, divisor = 3 Output: 3
Input: dividend = 7, divisor = -3 Output: -2

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

1⃣Определить знак результата и привести dividend и divisor к положительным значениям типа long, чтобы избежать переполнения и упростить работу с отрицательными числами.

2⃣Найти максимальное кратное делителя (удваивая divisor и счётчик divide), не превышающее dividend.

3⃣Рекурсивно вызвать деление для остатка dividend - sum, сложить с текущим divide и вернуть результат с учётом знака.

😎 Решение:

public class Solution {
    public int divide(int dividend, int divisor) {
        long result = divideLong(dividend, divisor);
        return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
    }

    private long divideLong(long dividend, long divisor) {
        boolean negative = dividend < 0 != divisor < 0;

        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);

        if (dividend < divisor) return 0;

        long sum = divisor;
        long divide = 1;
        while ((sum + sum) <= dividend) {
            sum += sum;
            divide += divide;
        }

        long remaining = divideLong(dividend - sum, divisor);
        return negative ? -(divide + remaining) : (divide + remaining);
    }
}

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