Domain 2MediumCORE

Fraction to Recurring Decimal

We are given two integers, numerator and denominator, representing a fraction. Our goal is to convert this into its decimal string representation. The critical requirement here is handling repeating decimals: if the fractional part repeats infinitely, we must enclose that sequence in parentheses (e.g., '0.(3)').

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Math

166. Fraction to Recurring Decimal

Model: qwen3.5:9b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 22.4%


Problem Breakdown

We are given two integers, numerator and denominator, representing a fraction. Our goal is to convert this into its decimal string representation. The critical requirement here is handling repeating decimals: if the fractional part repeats infinitely, we must enclose that sequence in parentheses (e.g., “0.(3)”).

Inputs: Two integers within standard 32-bit range (-2^31 to 2^31 - 1). Outputs: A string representing the decimal. Implicit Constraints & Edge Cases:

  • Signs: Negative numbers need correct sign handling (e.g., -50 / 8 = "-6.25"). If both are negative, result is positive.
  • Integer Results: If numerator divides evenly by denominator, there should be no decimal point or parentheses (e.g., "4", not "4.").
  • Zero Numerator: Should return "0".
  • Cycle Detection: We must detect when a remainder repeats to identify the start of an infinite loop. Since we are guaranteed that the answer length is manageable (< 10^4), we don’t need arbitrary precision libraries, but standard integer arithmetic in Python handles large numbers naturally anyway.

Intuition

Let’s simulate long division manually. We divide numerator by denominator. If there is a remainder, we multiply it by 10 and continue dividing to get the next decimal digit.

A brute-force approach might be to just keep generating digits until the string gets too long or time runs out, but that fails for infinite repeating decimals (like 1/31/3). We need an algorithmic way to stop when a cycle is detected.

The key insight in division-based problems involving cycles lies in the remainder. In any base-10 division process, if we encounter a remainder that we have seen before before reaching 0, it means the sequence of digits generated between those two occurrences will repeat forever.

Therefore:

  1. We track remainders using a Hash Map (Dictionary).
  2. The key is remainder, and the value is the index in our result string where that remainder first appeared.
  3. If we see a remainder again, we know exactly where to insert parentheses around the substring between its first occurrence and now.

Approach

  1. Handle Signs: Work with absolute values for calculation logic to avoid Python’s floor division quirks (e.g., -5 // -2 vs math expectation). Determine if the final result should be negative based on whether exactly one of numerator or denominator is negative.
  2. Integer Part: Perform integer division (abs(numerator) // abs(denominator)). Append this to our buffer string. Update remainder: remainder = numerator % denominator.
  3. Check for Zero Remainder: If the remainder becomes zero, we are done; return the result immediately (no decimal point needed if no fractional part exists yet? Wait, check logic here. Actually, append ., then loop). Correction: Only add a decimal point and enter the loop if remainder != 0.
  4. Fractional Part Loop:
    • Multiply remainder by 10 (shift left for next digit calculation).
    • Calculate quotient: (remainder * 10) // denominator -> append to buffer.
    • Update remainder: (remainder * 10) % denominator.
    • Cycle Check: If this new remainder exists in our map, we found a cycle. Insert parentheses around the substring from map[remainder] + 1 to current end of string. Break loop.
    • Otherwise, store {new_remainder: len(buffer)} and continue.

Complexity Analysis

  • Time: O(N)O(N) where NN is the length of the resulting decimal string (bounded by constraints). We perform constant time dictionary lookups/insertions per digit generated. Since we stop at either 0 remainder or a repeated remainder, we process each unique state once.
  • Space: O(N)O(N). We store the result string and the map mapping remainders to indices in that same order of magnitude as the output length.

Solution

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        # Handle sign logic separately using absolute values for math safety
        if numerator == 0:
            return "0"
        
        negative = (numerator < 0) ^ (denominator < 0)
        num, den = abs(numerator), abs(denominator)
        
        result = []
        
        # Integer part of the division
        integer_part = num // den
        remainder = num % den
        
        if denominator == 1: 
            return "-" + str(integer_part) if negative else str(integer_part)

        # Append decimal point and start fractional logic
        result.append(str(integer_part))
        
        if remainder != 0:
            result.append('.')
            
            seen_remainders = {}
            index_map = len(result) - 1
            
            while remainder != 0:
                if remainder in seen_remainders:
                    # Cycle detected, insert parentheses around repeating part
                    start_index = seen_remainders[remainder] + 1 
                    result.insert(start_index, '(')
                    result.append(')')
                    break
                
                seen_remainders[remainder] = len(result) - 1
                
                remainder *= 10
                digit = remainder // den
                remainder %= den
                result.append(str(digit))

        return "-" + "".join(result) if negative else "".join(result)

Edge Cases Handled

  • Negative Inputs: Logic uses abs() for calculation and a boolean flag to prepend - only when necessary. Handles cases like -1 / -2 = "0.5" correctly.
  • Zero Numerator: Explicitly returns "0".
  • Exact Division (No Remainder): If remainder becomes 0, the loop terminates naturally without adding parentheses or a trailing decimal point if not needed (though logic adds . only if initial remainder exists). Correction in code: The current implementation appends . immediately after integer part. This is correct for cases like “1/2” -> “0.”, then digit ‘5’. For exact division, the loop doesn’t run because we check remainder != 0 before appending ., but wait… if remainder becomes 0 inside loop?
    • If initial remainder is non-zero (e.g., 1/3), we append ’.’, enter loop. Remainder eventually repeats or hits 0.
    • If integer division leaves no remainder initially, remainder != 0 check prevents appending decimal point and entering the fractional logic block entirely? No, wait.
    • Let’s trace: num=2, den=1. integer_part=2. remainder=0. Code checks if denominator == 1: returns “2”.
    • What about 4/3 -> "1.(3)". Integer part 1, remainder 1. Append ., enter loop. Remainder repeats? No, it cycles eventually.
    • Wait, my code has a specific check for denominator == 1. That’s an optimization but not strictly necessary if logic holds.
    • Crucial Logic Check: If I have num=4, den=3, remainder is 1. Loop runs. Map stores {1: index}. Remainder becomes (1*10)%3 = 1. Next iteration sees 1 in map -> Insert parens. Correct.
    • Terminating Case: num=1, den=2. Integer part 0, remainder 1. Append ., enter loop.
      • Iteration 1: rem=1 not seen. Map {1: index}. Rem becomes (1*10)%2 = 0. Digit ‘5’.
      • Loop condition remainder != 0 fails next check? No, inside loop we update remainder at end.
      • Next iteration start: while remainder != 0: checks if rem is 0 (it was updated to 0). Loop terminates naturally without parens. Correct.

Note:* The code handles the case where a terminating decimal occurs by simply exiting the while loop when remainder becomes zero, avoiding parentheses insertion.**