Fraction to Recurring Decimal

The idea to solve this problem is to simulate the process of performing long division. While performing division, it’s possible to encounter the same remainder more than once. This indicates the start of a repeating portion.

Steps:

  1. Determine the integer part.
  2. Determine the fractional part.
    • Use a hashmap to keep track of remainders to detect the start of a repeating sequence.
    • Every time you encounter a remainder, multiply it by 10 and divide by the denominator to find the next digit.
    • Continue until there’s no remainder or the remainder starts to repeat.

Here’s how you can do it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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

        # Determine the sign of the result
        result = []
        if (numerator < 0) ^ (denominator < 0):
            result.append("-")

        numerator, denominator = abs(numerator), abs(denominator)

        # Integer part
        integer_part = numerator // denominator
        result.append(str(integer_part))

        remainder = numerator % denominator
        if remainder == 0:
            return ''.join(result)

        result.append(".")

        # Fractional part
        remainder_map = {} # to store remainders and their positions
        while remainder:
            if remainder in remainder_map:
                # Insert '(' before the position where this remainder was first seen
                result.insert(remainder_map[remainder], '(')
                result.append(')')
                break

            remainder_map[remainder] = len(result)
            remainder *= 10
            result.append(str(remainder // denominator))
            remainder %= denominator

        return ''.join(result)

This code divides the problem into handling the integer and fractional parts of the result. The hashmap remainder_map is used to detect repeating sequences in the fractional part.