Fraction To Recurring Decimal - Leetcode Solution

Problem Statement:

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.

Example 1:

Input: numerator = 1, denominator = 2

Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1

Output: "2"

Example 3:

Input: numerator = 2, denominator = 3

Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333

Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5

Output: "0.2"

Constraints:

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

denominator != 0

Solution:

Let's start by analyzing some examples. Let's look at the case of 1/2. The result is 0.5. Let's now look at the case of 2/3. The result is 0. (6), which means that the result is 0.666... and the 6 is repeating.

To solve the problem, we need to keep track of the remainder at each step. We can do this by creating a map that maps the remainder to the position where it occurs. At each step, we divide the numerator by the denominator and get the quotient and remainder. We append the quotient to the result string and then check if the remainder is already in the map. If it is, we enclose the repeating part in parentheses and return the result. If it is not, we add it to the map and continue with the next step.

Let's see the implementation of the above approach:

class Solution:

def fractionToDecimal(self, numerator: int, denominator: int) -> str:

    if numerator == 0:
        return "0"
    
    res = ""
    if (numerator < 0 and denominator > 0) or (numerator > 0 and denominator < 0):
        res += "-"
        
    numerator = abs(numerator)
    denominator = abs(denominator)
    res += str(numerator//denominator)
    remainder = numerator % denominator
    if remainder == 0:
        return res
    
    res += "."
    map = {}
    while remainder != 0:
        if remainder in map:
            index = map[remainder]
            res = res[:index] + "(" + res[index:] + ")"
            break
        map[remainder] = len(res)
        remainder *= 10
        res += str(remainder//denominator)
        remainder %= denominator
        
    return res

The time complexity of the above solution is O(N) where N is the maximum number of digits in the result. The space complexity is O(N) as well, since we need to keep track of the remainder at each step in the map.

1