Fraction to Recurring Decimal

Problem Description

Given two integers representing the numerator and denominator of a fraction, the task is to return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. The length of the answer string is guaranteed to be less than 10^4.

Naive Approach

A naive approach involves simply performing long division and keeping track of remainders and quotients. If a remainder repeats, we know that the fractional part is repeating. We can use a StringBuilder to construct the result string.

However, this approach doesn't handle negative numbers or integer overflow effectively. It also might be difficult to efficiently detect repeating remainders.

• Time Complexity: O(k), where k is the length of the fractional part.
• Space Complexity: O(k), to store the fractional part.

Optimal Approach

The optimal approach involves using a HashMap to keep track of remainders and their positions in the fractional part. This allows us to efficiently detect repeating remainders. We also need to handle negative numbers and potential integer overflow.

Here's a step-by-step breakdown:

1. Handle Signs: Determine the sign of the result and convert both numerator and denominator to positive numbers using Math.abs(). We XOR the signs of numerator and denominator to determine if the result should be negative.
2. Integer Part: Calculate the integer part of the fraction by dividing the absolute numerator by the absolute denominator.
3. Fractional Part:
   • Calculate the remainder of the division.
   • Use a HashMap to store remainders and their corresponding index in the StringBuilder.
   • In a loop, multiply the remainder by 10 and divide it by the denominator. Append the quotient to the StringBuilder.
   • If the remainder is already in the HashMap, it indicates a repeating fractional part. Insert parentheses at the appropriate index.
   • If the remainder becomes 0, the fractional part terminates.
4. Edge Cases:
   • Handle the case where the numerator is 0.
   • Handle integer overflow by using long type for intermediate calculations.

Here's the code:

import java.util.HashMap;

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

        StringBuilder result = new StringBuilder();
        // Determine the sign
        boolean negative = (numerator < 0) ^ (denominator < 0);
        if (negative) {
            result.append("-");
        }

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

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

        long remainder = num % den;
        if (remainder == 0) {
            return result.toString();
        }

        // Fractional part
        result.append(".");
        HashMap<Long, Integer> map = new HashMap<>();
        while (remainder != 0) {
            if (map.containsKey(remainder)) {
                int index = map.get(remainder);
                result.insert(index, "(");
                result.append(")");
                return result.toString();
            }
            map.put(remainder, result.length());
            remainder *= 10;
            quotient = remainder / den;
            result.append(quotient);
            remainder %= den;
        }

        return result.toString();
    }
}

• Time Complexity: O(k), where k is the length of the non-repeating and repeating parts of the fractional representation.
• Space Complexity: O(k), for the HashMap which stores the remainders and their positions.