unreasonably effective

link

The answer may look like: . For example: .

Details

• Since divmod(-1, 6) = (-1, 5), if we use remainder here, we would be finding decimal for . Instead we want the decimal for with negative sign. So, in the beginning we remember the sign and do all arithmetic operations on absolute values. In the end, we append sign.
• After first divmod, we get: whole, numerator2 = divmod(numerator, denominator). Here, numerator2 and denominator forms a proper fraction. So, we find repeated decimal using (numerator2, denominator).
• Although repeat happens in the decimal digits or quotients, it is easier to detect repeat using remainder. As soon as we see a remainder we have seen before, we know the quotient digits are going to repeat. So, our answer is the digits until that point. To find the boundary of not-repeated and repeated digits, we remember the position in the sequence of digits (or digit count up to then) where we see a remainder. If that position or index is , the not-repeated part is digits[0 : i] and repeated part is digits[i : ].

For q, r = divmod(numerator, denominator), . Consequently, the longest length before a fractional digit repeats is . The get_repeated_decimal()‘s outer loop can have these many iterations. On each of these iterations, the inner while loop can run for iterations.

So, time: , space: .

class Solution:
    def get_repeated_decimal(self, n, d):
        seen = {}
        digits = []
        while n > 0 and (n not in seen):
            seen[n] = len(digits)
            n *= 10
            while n < d:
                n *= 10
                digits.append(0)

            q, n = divmod(n, d)
            digits.append(q)

        if n == 0:
            return "".join(str(d) for d in digits)

        i = seen[n]
        not_repeated = "".join(str(d) for d in digits[:i])
        repeated = "".join(str(d) for d in digits[i:])
        return f"{not_repeated}({repeated})"

    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        is_negative = False if (numerator > 0) == (denominator > 0) else True
        numerator, denominator = abs(numerator), abs(denominator)

        whole, numerator = divmod(numerator, denominator)

        fraction = self.get_repeated_decimal(numerator, denominator)

        decimal = (
            ("-" if is_negative else "")
            + str(whole)
            + (f".{fraction}" if fraction else "")
        )
        return decimal