Solution Explanation: Fraction to Recurring Decimal

This problem involves converting a fraction (represented by its numerator and denominator) into its decimal representation, handling both terminating and repeating decimals.

Approach:

The solution utilizes a combination of mathematical operations and a hash table (or dictionary in Python) to efficiently detect and represent repeating decimal patterns. Here's a breakdown:

1. Handle Trivial Cases:

   • If the numerator is 0, the result is simply "0".

2. Determine Sign:

   • Check the signs of the numerator and denominator. If they differ, the decimal will be negative. Store this information for later.

3. Integer Part:

   • Perform integer division (numerator // denominator in Python, / in other languages) to get the integer part of the decimal.

4. Remainder:

   • Calculate the remainder using the modulo operator (%). This remainder is crucial for determining the fractional part.

5. Handle Zero Remainder:

   • If the remainder is 0, the fraction is a terminating decimal, and we are done. We concatenate the integer part and return the result.

6. Fractional Part (Repeating Decimal Detection):

   • This is the core of the solution. We maintain a hash table (or dictionary) to keep track of remainders encountered so far. The key is the remainder and the value is the index (or position) in the decimal string where that remainder first occurred.
   • We iteratively perform the following:
     • Multiply the remainder by 10 (to shift to the next decimal place).
     • Perform integer division by the denominator to get the next digit.
     • Append this digit to the result string.
     • Calculate the new remainder.
     • Check if the remainder is already in the hash table:
       • If found: A repeating pattern is detected. Insert a '(' at the index where the repeating remainder first appeared, append ')', and return the result string.
       • If not found: Add the remainder and its current index to the hash table and continue the iteration.

Time Complexity: O(l), where l is the length of the resulting decimal string. In the worst case (a long repeating pattern), we might iterate through the algorithm many times. The problem statement guarantees that l < 10^4.

Space Complexity: O(l) - the hash table stores at most l entries (remainders).

Code Examples (Python and Java):

Python:

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
 
        sign = "-" if (numerator > 0) ^ (denominator > 0) else ""
        numerator, denominator = abs(numerator), abs(denominator)
 
        integer_part = numerator // denominator
        remainder = numerator % denominator
 
        if remainder == 0:
            return sign + str(integer_part)
 
        fractional_part = ""
        remainder_map = {}  # Dictionary to track remainders
        index = 0
 
        while remainder != 0 and remainder not in remainder_map:
            remainder_map[remainder] = index
            remainder *= 10
            fractional_part += str(remainder // denominator)
            remainder %= denominator
            index += 1
 
        if remainder == 0:
            return sign + str(integer_part) + "." + fractional_part
        else:
            repeat_index = remainder_map[remainder]
            return sign + str(integer_part) + "." + fractional_part[:repeat_index] + "(" + fractional_part[repeat_index:] + ")"
 

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
 
        String sign = ((numerator > 0) ^ (denominator > 0)) ? "-" : "";
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
 
        long integerPart = num / den;
        long remainder = num % den;
 
        if (remainder == 0) {
            return sign + integerPart;
        }
 
        StringBuilder fractionalPart = new StringBuilder();
        Map<Long, Integer> remainderMap = new HashMap<>();
        int index = 0;
 
        while (remainder != 0 && !remainderMap.containsKey(remainder)) {
            remainderMap.put(remainder, index);
            remainder *= 10;
            fractionalPart.append(remainder / den);
            remainder %= den;
            index++;
        }
 
        if (remainder == 0) {
            return sign + integerPart + "." + fractionalPart;
        } else {
            int repeatIndex = remainderMap.get(remainder);
            return sign + integerPart + "." + fractionalPart.substring(0, repeatIndex) + "(" + fractionalPart.substring(repeatIndex) + ")";
        }
    }
}

The other languages (C++, Go, TypeScript, C#) follow similar logic, adapting the data structures and syntax as needed for each language. The core algorithm remains consistent across all implementations.