Problem statement

https://leetcode.com/problems/fraction-to-recurring-decimal/

Solution

Implement long division: if we want to divide x by y, first we find the integer part, and for every new digit we multiply reminder by 10 and find new digit and new reminder. Do not forget about signs, also there is 3 parts: integer part, preperiod and period. To understand, where period starts, we need to keep the dictionary of all reminders and stop when we see the repetition. Also take care if period is equal to (0).

Complexity

Time and memory complexity is O(n), where n is lengh of preperiod and period

Code

class Solution:
    def fractionToDecimal(self, x, y):
        n, rem = divmod(abs(x), abs(y))
        sign = '-' if x*y < 0 else ''
        x, y = abs(x), abs(y)
        result = [sign + str(n), '.']
        rems = {}

        while rem > 0 and rem not in rems:
            rems[rem] = len(result)
            n, rem = divmod(rem*10, y)
            result += [str(n)]

        if rem in rems:
            idx = rems[rem]
            result.insert(idx, '(')
            result += [')']

        return ''.join(result).rstrip(".")