Задача: 166. Fraction to Recurring Decimal
Сложность: medium

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

1⃣Использование хеш-таблицы для отслеживания остатков:
Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.
Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.

2⃣Обработка нулевого остатка:
Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.

3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

class Solution {
    function fractionToDecimal($numerator, $denominator) {
        if ($numerator == 0) {
            return "0";
        }

        $fraction = "";
        if (($numerator < 0) xor ($denominator < 0)) {
            $fraction .= "-";
        }

        $dividend = abs($numerator);
        $divisor = abs($denominator);

        $fraction .= intval($dividend / $divisor);
        $remainder = $dividend % $divisor;
        if ($remainder == 0) {
            return $fraction;
        }

        $fraction .= ".";
        $lookup = [];
        while ($remainder != 0) {
            if (isset($lookup[$remainder])) {
                $pos = $lookup[$remainder];
                $fraction = substr($fraction, 0, $pos) . "(" . substr($fraction, $pos) . ")";
                break;
            }
            $lookup[$remainder] = strlen($fraction);
            $remainder *= 10;
            $fraction .= intval($remainder / $divisor);
            $remainder %= $divisor;
        }

        return $fraction;
    }
}

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