🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: №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)
