166. Fraction to Recurring Decimal

Level - medium

Task

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

Объяснение

Задача заключается в том, чтобы преобразовать дробь, представленную в виде пары целых чисел (числитель и знаменатель), в строку, которая представляет десятичное представление этой дроби. Важным аспектом задачи является правильное отображение повторяющихся десятичных знаков, если таковые имеются.

Основные шаги решения задачи:

1. Обработка целой части. Если дробь неправильная (числитель больше или равен знаменателю), сначала нужно выделить целую часть дроби. Это делается путем деления числителя на знаменатель нацело.
2. Обработка дробной части. После выделения целой части, остаток от деления числителя на знаменатель будет использоваться для вычисления дробной части. Этот остаток умножается на 10 и делится на знаменатель, чтобы получить первую цифру после запятой.
3. Обнаружение повторяющихся последовательностей. Для обнаружения повторяющихся десятичных знаков можно использовать словарь (или хэш-таблицу), где ключом будет остаток от деления, а значением — позиция, на которой этот остаток впервые появился в результате. Если остаток повторяется, это означает, что десятичная часть начинает повторяться с этой позиции.
4. Форматирование результата Результат должен быть отформатирован так, чтобы повторяющиеся десятичные знаки были заключены в скобки. Например, дробь 1/3 должна быть представлена как "0.(3)".

Example 1:

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

Example 2:

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

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

-2^31 <= numerator, denominator <= 2^31 - 1 denominator != 0