Fraction to Recurring Decimal

• Handle the sign and integer part of the fraction as usual, using long to prevent overflow.
• If there is a fractional part, initialize an ArrayList to store the remainders encountered during the long division process.
• Begin a loop to calculate the digits of the fractional part.
• In each step, before processing the current remainder, check if it already exists in the list of remainders by performing a linear scan (list.contains(remainder)). This check takes time proportional to the number of digits generated so far.
• If the remainder is found, a cycle is detected. Find its index in the list (list.indexOf(remainder)) to determine where the repeating part starts. Format the output string with parentheses and return.
• If the remainder is new, add it to the list, and continue the long division: multiply the remainder by 10, calculate the next digit, and find the new remainder.
• If the remainder becomes 0, the fraction is terminating. Append the calculated fractional part and return.

This approach correctly solves the problem by simulating long division. The core idea is to keep track of the remainders generated at each step of the division of the fractional part. A repeating remainder signals the beginning of a repeating sequence of digits.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String fractionToDecimal(int numerator, int denominator) {6        if (numerator == 0) {7            return "0";8        }9        StringBuilder res = new StringBuilder();10        if ((numerator > 0) ^ (denominator > 0)) {11            res.append("-");12        }13        long num = Math.abs((long) numerator);14        long den = Math.abs((long) denominator);15        res.append(num / den);16        long rem = num % den;17        if (rem == 0) {18            return res.toString();19        }20        res.append(".");21        22        StringBuilder fractionPart = new StringBuilder();23        List<Long> remainderList = new ArrayList<>();24        25        while (rem != 0) {26            if (remainderList.contains(rem)) {27                int startIndex = remainderList.indexOf(rem);28                res.append(fractionPart.substring(0, startIndex));29                res.append("(");30                res.append(fractionPart.substring(startIndex));31                res.append(")");32                return res.toString();33            }34            35            remainderList.add(rem);36            rem *= 10;37            fractionPart.append(rem / den);38            rem %= den;39        }40        41        res.append(fractionPart);42        return res.toString();43    }44}

In this implementation, we use an ArrayList to store the remainders. The contains and indexOf methods on an ArrayList both perform a linear scan, which takes O(N) time, where N is the current size of the list. Since the list can grow up to the size of the denominator, this lookup becomes the bottleneck.

• Handle the trivial case where the numerator is 0.
• Determine the sign of the result. If the numerator and denominator have opposite signs, the result is negative. Prepend a "-" to the result StringBuilder.
• Convert the numerator and denominator to long and take their absolute values to prevent integer overflow and simplify calculations.
• Calculate the integer part of the fraction (num / den) and append it to the result.
• Calculate the initial remainder (num % den). If the remainder is 0, the division is exact, and we can return the result.
• If there is a remainder, append a decimal point "." to the result.
• Initialize a HashMap<Long, Integer> to store remainders as keys and their corresponding positions (indices) in the result string as values.
• Enter a loop that continues as long as the remainder is not zero.
• Inside the loop, check if the current remainder already exists in the HashMap. This is an O(1) average time operation.
• If it does, a repeating cycle has been found. Retrieve the index start where this remainder first appeared. Insert an opening parenthesis ( at that index in the result string and append a closing parenthesis ) at the end. Then, break the loop.
• If the remainder is new, add it to the HashMap with the current length of the result string as its position: map.put(remainder, result.length()).
• Proceed with the long division: multiply the remainder by 10, append the integer quotient of this new number and the denominator (remainder * 10 / den) to the result, and update the remainder to be the new remainder (remainder * 10 % den).
• Once the loop terminates (either by finding a cycle or the remainder becoming zero), return the final string from the StringBuilder.

This optimal solution simulates long division while using a HashMap to efficiently detect repeating remainders. A repeating remainder indicates the start of a recurring cycle in the decimal expansion.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public String fractionToDecimal(int numerator, int denominator) {6        if (numerator == 0) {7            return "0";8        }9 10        StringBuilder result = new StringBuilder();11        // Step 1: Determine the sign12        if ((numerator > 0) ^ (denominator > 0)) {13            result.append("-");14        }15 16        // Step 2: Use long to avoid overflow and work with absolute values17        long num = Math.abs((long) numerator);18        long den = Math.abs((long) denominator);19 20        // Step 3: Append the integer part21        result.append(num / den);22        long remainder = num % den;23 24        // Step 4: If remainder is 0, we are done25        if (remainder == 0) {26            return result.toString();27        }28 29        // Step 5: Append the decimal point30        result.append(".");31 32        // Step 6: Use a map to track remainders and their positions33        Map<Long, Integer> remainderMap = new HashMap<>();34        35        // Step 7: Simulate long division for the fractional part36        while (remainder != 0) {37            // Step 8: Check for repeating remainder38            if (remainderMap.containsKey(remainder)) {39                int startIndex = remainderMap.get(remainder);40                result.insert(startIndex, "(");41                result.append(")");42                break;43            }44 45            // Step 9: Store the remainder and its position46            remainderMap.put(remainder, result.length());47 48            // Step 10: Continue long division49            remainder *= 10;50            result.append(remainder / den);51            remainder %= den;52        }53 54        return result.toString();55    }56}

By using a HashMap, checking for a previously seen remainder becomes an O(1) operation on average. This significantly improves the time complexity compared to a linear search, making the algorithm efficient enough to handle large denominators within the given constraints.