We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Fraction to Recurring Decimal

Difficulty: Medium

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. If multiple answers are possible, return any of them. It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.

Key Insights

  • Handle both the integer and fractional parts of the division.
  • Use a hash table to track remainders and their corresponding positions in the result string to detect cycles.
  • Properly format the result string to include parentheses for repeating decimals.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the decimal part of the fraction. Space Complexity: O(n), where n is the number of unique remainders encountered.

Solution

To convert a fraction into a string representation, we can follow these steps:

  1. Determine the sign of the result based on the numerator and denominator.
  2. Compute the integer part of the fraction using integer division.
  3. Use the modulo operation to find the remainder and handle the fractional part.
  4. Use a hash table (dictionary) to map remainders to their positions in the resulting string to identify repeating cycles.
  5. Format the output string by adding parentheses around the repeating part if a cycle is detected.

Code Solutions

def fractionToDecimal(numerator: int, denominator: int) -> str:
    if numerator == 0:
        return "0"
    
    # Determine the sign of the result
    sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
    
    # Work with absolute values
    numerator, denominator = abs(numerator), abs(denominator)
    
    # Integer part
    integer_part = numerator // denominator
    result = sign + str(integer_part)
    
    # Remainder and fractional part
    remainder = numerator % denominator
    if remainder == 0:
        return result
    
    result += "."
    remainder_map = {}
    fraction_part = ""
    
    while remainder != 0:
        # If the remainder has been seen before, we have a repeating fraction
        if remainder in remainder_map:
            index = remainder_map[remainder]
            fraction_part = fraction_part[:index] + "(" + fraction_part[index:] + ")"
            break
        
        # Record the position of this remainder
        remainder_map[remainder] = len(fraction_part)
        
        remainder *= 10
        fraction_part += str(remainder // denominator)
        remainder %= denominator
    
    result += fraction_part
    return result
← Back to All Questions