LeetCode 166: Fraction to Recurring Decimal Solution in Python Explained

Problem Statement

In LeetCode 166, you’re given two integers numerator and denominator representing a fraction. Your task is to return the fraction as a string:

• If the result is an integer, return it (e.g., "2").
• If there’s a fractional part, include it (e.g., "0.5").
• If the fractional part recurs, enclose the recurring part in parentheses (e.g., "0.(6)").

The result fits within a 32-bit signed integer. This differs from version comparison like LeetCode 165: Compare Version Numbers, focusing on decimal conversion rather than string ordering.

Constraints

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0
• Result fits in a 32-bit signed integer

Example

Let’s see some cases:

Copy codeInput: numerator = 1, denominator = 2
Output: "0.5"
Explanation: 1/2 = 0.5, no recurring part.

Copy codeInput: numerator = 2, denominator = 1
Output: "2"
Explanation: 2/1 = 2, integer result.

Copy codeInput: numerator = 4, denominator = 333
Output: "0.(012)"
Explanation: 4/333 = 0.012012..., recurring "012".

Copy codeInput: numerator = -50, denominator = 8
Output: "-6.25"
Explanation: -50/8 = -6.25, no recurring part.

These examples show we’re converting fractions to decimals.

Understanding the Problem

How do you solve LeetCode 166: Fraction to Recurring Decimal in Python? Take numerator = 1, denominator = 2. It’s 0.5, so "0.5". For 2/1, it’s 2, so "2". For 4/333, it’s 0.012012…, recurring "012", so "0.(012)". For -50/8, it’s -6.25, so "-6.25". We need to handle signs, integer parts, and detect recurring decimals efficiently, not an array task like LeetCode 164: Maximum Gap. We’ll use: 1. Long Division with Hash Map: O(n) time, O(n) space—our best solution. 2. String Manipulation with Precomputed Fractions: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Long Division with Hash Map Approach

Explanation

Long Division with Hash Map simulates long division, tracking remainders to detect recurrence:

• Handle the sign, compute absolute values.
• Compute integer part, append to result.
• For the fractional part, use long division:
• Multiply remainder by 10, divide by denominator.
• Track remainders in a hash map with their positions.
• If a remainder repeats, mark the recurring part.
• Format the result string.

This is the best solution due to its O(n) time complexity (n = digits in result), O(n) space (hash map), and precise handling of recurring decimals, making it efficient and robust.

For 4/333:

• Integer: 0.
• Fractional: 4→12→120→120 (repeats), "0.(012)".

Step-by-Step Example

Example 1: numerator = 1, denominator = 2

Goal: Return "0.5".

• Start: sign = 1, num = 1, den = 2.
• Step 1: Integer part.
• integer = 1 // 2 = 0, remainder = 1 % 2 = 1.
• result = "0".
• Step 2: Fractional part.
• remainder = 1, seen = {{.
• 1×10=10, 10//2=5, remainder = 10%2=0, append "5".
• result = "0.5", remainder = 0, stop.
• Finish: Return "0.5".

Example 2: numerator = 4, denominator = 333

Goal: Return "0.(012)".

• Step 1: integer = 0, remainder = 4, result = "0".
• Step 2: Fractional part.
• remainder = 4, seen = {{.
• 4×10=40, 40//333=0, remainder = 40, append "0", seen = {40:1{.
• 40×10=400, 400//333=1, remainder = 67, append "1", seen = {40:1,67:2{.
• 67×10=670, 670//333=2, remainder = 4, seen[4]=1, repeat at pos 1.
• result = "0.012", insert "(" at 1, append ")", "0.(012)".
• Finish: Return "0.(012)".

Example 3: numerator = -50, denominator = 8

Goal: Return "-6.25".

• Step 1: sign = -1, num = 50, den = 8.
• integer = 50 // 8 = 6, remainder = 2, result = "-6".
• Step 2: Fractional part.
• 2×10=20, 20//8=2, remainder = 4, append "2".
• 4×10=40, 40//8=5, remainder = 0, append "5".
• result = "-6.25", stop.
• Finish: Return "-6.25".

How the Code Works (Long Division with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef fractionToDecimal(numerator: int, denominator: int) -> str:
    # Line 1: Handle sign
    if numerator == 0:
        # Zero numerator (e.g., 0/2)
        return "0"
    sign = -1 if (numerator < 0) ^ (denominator < 0) else 1
    # XOR for sign (e.g., -50/8 → -1)
    num = abs(numerator)
    # Absolute numerator (e.g., 50)
    den = abs(denominator)
    # Absolute denominator (e.g., 8)

    # Line 2: Compute integer part
    integer = num // den
    # Integer quotient (e.g., 6)
    remainder = num % den
    # Initial remainder (e.g., 2)
    result = "-" + str(integer) if sign == -1 else str(integer)
    # Start result (e.g., "-6")
    if remainder == 0:
        # No fractional part (e.g., 2/1)
        return result

    # Line 3: Initialize fractional part
    result += "."
    # Append decimal point (e.g., "-6.")
    seen = {{
    # Remainder positions (e.g., {{)

    # Line 4: Compute fractional part
    while remainder != 0:
        # Continue until remainder zero (e.g., 2)
        if remainder in seen:
            # Recurrence detected (e.g., 4 repeats)
            pos = seen[remainder]
            # Position of repeat (e.g., 1)
            return result[:pos] + "(" + result[pos:] + ")"
            # Format recurring (e.g., "0.(012)")

        seen[remainder] = len(result)
        # Record position (e.g., {40:2{)
        remainder *= 10
        # Next digit (e.g., 20)
        digit = remainder // den
        # Current digit (e.g., 2)
        result += str(digit)
        # Append digit (e.g., "-6.2")
        remainder %= den
        # Update remainder (e.g., 4)

    # Line 5: Return final result
    return result
    # e.g., "-6.25"

This detailed breakdown clarifies how long division with a hash map efficiently converts fractions.

Alternative: String Manipulation with Precomputed Fractions Approach

Explanation

String Manipulation with Precomputed Fractions builds the decimal by precomputing digits:

• Compute integer part, handle sign.
• For fractional part, simulate division up to a limit, checking for repetition manually.
• Format the result string.

It’s a practical alternative, O(n) time (n = digits), O(n) space (string storage), but less elegant and potentially less precise due to fixed limits.

For 4/333:

• Integer: 0.
• Fractional: "012" repeats, "0.(012)".

Step-by-Step Example (Alternative)

For 1/2:

• Step 1: Integer=0, remainder=1.
• Step 2: Digits: "5", remainder=0, "0.5".
• Finish: Return "0.5".

How the Code Works (String Manipulation)

Copy codedef fractionToDecimalString(numerator: int, denominator: int) -> str:
    if numerator == 0:
        return "0"
    sign = -1 if (numerator < 0) ^ (denominator < 0) else 1
    num, den = abs(numerator), abs(denominator)
    integer = num // den
    remainder = num % den
    result = "-" + str(integer) if sign == -1 else str(integer)
    if remainder<|control302|>        result += "."
        digits = []
        seen = {{
        while remainder and len(digits) < 1000:  # Arbitrary limit
            if remainder in seen:
                pos = seen[remainder]
                return result + digits[:pos] + "(" + digits[pos:] + ")"
            seen[remainder] = len(digits)
            remainder *= 10
            digit = remainder // den
            digits.append(str(digit))
            remainder %= den
        result += "".join(digits)
    return result

Complexity

• Long Division with Hash Map:
• Time: O(n) – digits in result.
• Space: O(n) – hash map.
• String Manipulation with Precomputed Fractions:
• Time: O(n) – digits up to limit.
• Space: O(n) – digit list.

Efficiency Notes

Long Division with Hash Map is the best solution with O(n) time and O(n) space, offering precision and clarity—String Manipulation with Precomputed Fractions matches time complexity but uses a less robust approach with arbitrary limits, still requiring O(n) space.

Key Insights

• Long Division: Exact recurrence.
• Hash Map: Detects cycles.
• String: Builds manually.

Additional Example

For numerator = 1, denominator = 6:

• Goal: "0.1(6)".
• Long Division: 1/6=0.1666…, "0.1(6)".

Edge Cases

• Zero: 0/5 → "0".
• Integer: 2/1 → "2".
• Negative: -1/2 → "-0.5".

Both solutions handle these well.

Final Thoughts

LeetCode 166: Fraction to Recurring Decimal in Python is a delightful math-to-string challenge. The Long Division with Hash Map solution excels with its efficiency and precision, while String Manipulation with Precomputed Fractions offers an alternative approach. Want more? Try LeetCode 12: Integer to Roman for number conversion or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 166 on LeetCode with 4 and 333, aiming for "0.(012)"—test your skills now!