LeetCode 166: Fraction to Recurring Decimal - From Intuitive to Optimized (Java, Med)

• Topics: Hash Table, Math, String

Problem Overview

The "Fraction to Recurring Decimal" problem asks us to convert a fraction (given as numerator and denominator) into its string representation. The key challenge is detecting and properly formatting repeating decimal patterns.

Given: Two integers numerator and denominator
Goal: Return the fraction as a string, with repeating decimals enclosed in parentheses

Examples:

• 1/2 → "0.5"
• 2/1 → "2"
• 4/333 → "0.(012)"

Key Insights

1. Long Division Algorithm: We simulate the manual long division process
2. Cycle Detection: When we encounter a remainder we've seen before, we've found the repeating cycle
3. Edge Cases: Handle negative numbers, integer results, and overflow scenarios

Solution 1: Intuitive Approach with StringBuilder

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        StringBuilder result = new StringBuilder();

        // Handle negative sign
        if ((numerator < 0) ^ (denominator < 0)) {
            result.append('-');
        }

        // Convert to positive long to avoid overflow
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        // Integer part
        result.append(num / den);
        num %= den;

        if (num == 0) return result.toString();

        // Decimal part
        result.append('.');
        Map<Long, Integer> remainderMap = new HashMap<>();

        while (num != 0) {
            // If we've seen this remainder before, we have a cycle
            if (remainderMap.containsKey(num)) {
                int index = remainderMap.get(num);
                result.insert(index, '(');
                result.append(')');
                break;
            }

            // Remember the position of this remainder
            remainderMap.put(num, result.length());

            // Continue long division
            num *= 10;
            result.append(num / den);
            num %= den;
        }

        return result.toString();
    }
}

How It Works

This solution follows the intuitive long division process:

1. Handle the sign and integer part first
2. For the decimal part, keep track of remainders and their positions
3. When we encounter a repeated remainder, insert parentheses to mark the cycle
4. Use StringBuilder.insert() to add the opening parenthesis at the cycle start

Time Complexity: O(d) where d is the number of decimal digits
Space Complexity: O(d) for the remainder map and result string

Solution 2: Optimized Single-Pass Approach

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        StringBuilder sb = new StringBuilder();

        // Handle sign
        if ((numerator < 0) ^ (denominator < 0)) {
            sb.append('-');
        }

        // Convert to positive long to handle overflow
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        // Integer part
        sb.append(num / den);
        num %= den;

        if (num == 0) return sb.toString();

        // Decimal part
        sb.append('.');
        Map<Long, Integer> map = new HashMap<>();

        while (num != 0) {
            if (map.containsKey(num)) {
                int index = map.get(num);
                sb.insert(index, '(');
                sb.append(')');
                return sb.toString();
            }

            map.put(num, sb.length());
            num *= 10;
            sb.append(num / den);
            num %= den;
        }

        return sb.toString();
    }
}

How It Works

This optimized version eliminates the need for a separate break statement by returning immediately when a cycle is detected. The logic remains the same but is more streamlined.

Time Complexity: O(d) where d is the number of decimal digits
Space Complexity: O(d) for the remainder map and result string

Solution 3: Memory-Optimized Approach

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        StringBuilder sb = new StringBuilder();

        // Handle sign
        if ((numerator < 0) ^ (denominator < 0)) {
            sb.append('-');
        }

        // Use long to avoid overflow
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        // Integer part
        sb.append(num / den);
        num %= den;

        if (num == 0) return sb.toString();

        // Decimal part
        sb.append('.');

        // Use a more memory-efficient approach
        Map<Long, Integer> remainderIndex = new HashMap<>();
        List<Character> decimalPart = new ArrayList<>();

        while (num != 0) {
            if (remainderIndex.containsKey(num)) {
                int cycleStart = remainderIndex.get(num);
                // Build the result with parentheses
                for (int i = 0; i < cycleStart; i++) {
                    sb.append(decimalPart.get(i));
                }
                sb.append('(');
                for (int i = cycleStart; i < decimalPart.size(); i++) {
                    sb.append(decimalPart.get(i));
                }
                sb.append(')');
                return sb.toString();
            }

            remainderIndex.put(num, decimalPart.size());
            num *= 10;
            decimalPart.add((char) ('0' + num / den));
            num %= den;
        }

        // No cycle found, append all decimal digits
        for (char digit : decimalPart) {
            sb.append(digit);
        }

        return sb.toString();
    }
}

Mathematical Foundation

The algorithm is based on the long division process:

1. Integer Division: numerator ÷ denominator gives the integer part
2. Remainder Processing: The remainder becomes the new numerator
3. Decimal Generation: Multiply remainder by 10 and divide by denominator
4. Cycle Detection: When a remainder repeats, we've found the cycle

Why This Works

In long division, if we encounter the same remainder twice, the subsequent digits will repeat exactly. This is because:

• Same remainder + same denominator = same quotient and same new remainder
• This creates a deterministic cycle

Edge Cases and Considerations

1. Overflow Handling

// Critical: Use long to avoid integer overflow
long num = Math.abs((long) numerator);
long den = Math.abs((long) denominator);

2. Sign Handling

// XOR to check if exactly one number is negative
if ((numerator < 0) ^ (denominator < 0)) {
    result.append('-');
}

3. Integer Results

// Check if there's no fractional part
if (num == 0) return result.toString();

Performance Analysis

Where d is the number of decimal digits before repetition.

Key Takeaways

1. Long Division Simulation: The core algorithm simulates manual long division
2. Remainder Tracking: Using a HashMap to track remainders and their positions is crucial
3. Overflow Prevention: Always use long for calculations to handle edge cases
4. Cycle Detection: The mathematical property that repeated remainders create cycles is the key insight

When to Use Each Solution

Solution 1 (Intuitive): Best for interviews and learning - clear logic flow
Solution 2 (Optimized): Good balance of readability and efficiency
Solution 3 (Memory-Optimized): When performance is critical and insert() operations are expensive

The problem beautifully demonstrates how mathematical insights (long division properties) can be translated into efficient algorithmic solutions while handling various edge cases and constraints.