LeetCode Solutions Blog

Fraction to Recurring Decimal

Number: 166

Difficulty: Medium

Paid? No

Problem Description

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.

Key Insights

Determine the sign of the result using the signs of the numerator and denominator.
Convert both the numerator and denominator to their absolute values to simplify further calculations.
Use integer division to compute the integral (whole) part of the result.
For the fractional part, use remainder and a hash table (dictionary) to detect cycles.
When a cycle is found, insert parentheses around the repeating sequence in the decimal part.

Space and Time Complexity

Time Complexity: O(n) where n is the number of digits in the fractional part until a repeat is found. Space Complexity: O(n) due to storing the remainders and their positions in a hash table.

Solution

The solution first handles the sign of the result. It computes the integral part of the fraction with simple division. For the fractional part, the key is to track remainders using a hash table. At each step, the current remainder multiplied by 10 gives the next digit in the decimal representation. If a remainder repeats, it indicates the start of a recurring cycle; the solution then inserts parentheses around the repeating part. Edge cases, such as when there is no remainder (i.e., the division is exact), are also handled.

Code Solutions

# Python solution for Fraction to Recurring Decimal

def fractionToDecimal(numerator, denominator):
    # if numerator is 0, the result is "0"
    if numerator == 0:
        return "0"

    result = []
    
    # Determine the sign. Negative if exactly one of numerator / denominator are negative.
    if (numerator < 0) ^ (denominator < 0):
        result.append("-")
    
    # Convert the numbers to absolute values.
    num = abs(numerator)
    den = abs(denominator)
    
    # Append the integral part.
    result.append(str(num // den))
    
    # Compute the remainder.
    remainder = num % den
    if remainder == 0:
        return "".join(result)
    
    # Append the decimal point.
    result.append(".")
    
    # Dictionary to store previously seen remainders and their corresponding index in result.
    remainder_map = {}
    
    # Process the fractional part.
    while remainder != 0:
        # If the remainder is already seen, a cycle has been detected.
        if remainder in remainder_map:
            # Insert parentheses around the repeating part.
            index = remainder_map[remainder]
            result.insert(index, "(")
            result.append(")")
            break
        
        # Store the index in the result list when this remainder is first seen.
        remainder_map[remainder] = len(result)
        
        # Multiply the remainder by 10 for the next digit.
        remainder *= 10
        result.append(str(remainder // den))
        
        # Update the remainder.
        remainder %= den
        
    return "".join(result)

# Example usage:
# print(fractionToDecimal(4, 333)) # Output: "0.(012)"