Code Implementation

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        res = []
        # Determine the sign
        if (numerator < 0) != (denominator < 0):
            res.append('-')
        numerator, denominator = abs(numerator), abs(denominator)
        # Integer part
        res.append(str(numerator // denominator))
        remainder = numerator % denominator
        if remainder == 0:
            return ''.join(res)
        res.append('.')
        # Fractional part
        rem_pos = {}
        while remainder:
            if remainder in rem_pos:
                res.insert(rem_pos[remainder], '(')
                res.append(')')
                break
            rem_pos[remainder] = len(res)
            remainder *= 10
            res.append(str(remainder // denominator))
            remainder %= denominator
        return ''.join(res)
      

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string res;
        // Sign
        if ((numerator < 0) ^ (denominator < 0)) res += "-";
        long num = labs(numerator);
        long den = labs(denominator);
        // Integer part
        res += to_string(num / den);
        long rem = num % den;
        if (rem == 0) return res;
        res += ".";
        unordered_map<long, int> rem_pos;
        while (rem) {
            if (rem_pos.count(rem)) {
                res.insert(rem_pos[rem], 1, '(');
                res += ")";
                break;
            }
            rem_pos[rem] = res.size();
            rem *= 10;
            res += to_string(rem / den);
            rem %= den;
        }
        return res;
    }
};
      

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        StringBuilder res = new StringBuilder();
        // Sign
        if ((numerator < 0) ^ (denominator < 0)) res.append("-");
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
        // Integer part
        res.append(num / den);
        long rem = num % den;
        if (rem == 0) return res.toString();
        res.append(".");
        Map<Long, Integer> remPos = new HashMap<>();
        while (rem != 0) {
            if (remPos.containsKey(rem)) {
                res.insert(remPos.get(rem), "(");
                res.append(")");
                break;
            }
            remPos.put(rem, res.length());
            rem *= 10;
            res.append(rem / den);
            rem %= den;
        }
        return res.toString();
    }
}
      

var fractionToDecimal = function(numerator, denominator) {
    if (numerator === 0) return "0";
    let res = '';
    // Sign
    if ((numerator < 0) !== (denominator < 0)) res += '-';
    let num = Math.abs(numerator);
    let den = Math.abs(denominator);
    // Integer part
    res += Math.floor(num / den);
    let rem = num % den;
    if (rem === 0) return res;
    res += '.';
    let remPos = {};
    while (rem) {
        if (rem in remPos) {
            res = res.slice(0, remPos[rem]) + '(' + res.slice(remPos[rem]) + ')';
            break;
        }
        remPos[rem] = res.length;
        rem *= 10;
        res += Math.floor(rem / den);
        rem %= den;
    }
    return res;
};
      

Problem Description

Given two integers, numerator and denominator, return the fraction as a string in decimal form. If the fractional part is repeating, enclose the repeating part in parentheses.

Key constraints:

• There will always be exactly one valid output for each input pair.
• Both numerator and denominator can be negative or zero.
• If the fractional part is repeating, only the repeating part should be enclosed in parentheses.
• Do not round or truncate; express the exact decimal representation.
• Examples:
  • numerator = 1, denominator = 2 → "0.5"
  • numerator = 2, denominator = 3 → "0.(6)"
  • numerator = 4, denominator = 333 → "0.(012)"

Thought Process

To solve this problem, we need to simulate division and keep track of repeating decimals. At first, you might think of simply dividing numerator by denominator using floating-point arithmetic, but this will not handle repeating decimals or the requirement to enclose repeated parts in parentheses.

The key insight is that repeating decimals occur when the same remainder appears again during the division process. By tracking remainders and their positions in the result, we can detect the start of a repeating sequence. This is similar to how you would perform long division by hand, writing down each step and noticing when a remainder repeats.

We also need to handle edge cases such as negative numbers, zero, and when the division results in no fractional part.

Solution Approach

We can break the solution down into the following steps:

1. Handle Zero Numerator: If numerator is zero, the result is simply "0".
2. Determine the Sign: The result is negative if exactly one of numerator or denominator is negative. We append a '-' sign if necessary.
3. Work with Absolute Values: To avoid sign issues, convert both numbers to their absolute values for the calculation.
4. Get the Integer Part: Divide numerator by denominator to get the integer part. Append this to the result.
5. Check for Remainder: If there is no remainder, return the result as there is no fractional part.
6. Fractional Part Calculation: If there is a remainder, begin calculating the fractional part:
   • Multiply the remainder by 10 and divide by denominator to get each digit after the decimal point.
   • Keep a hash map (or dictionary) that maps each remainder to its position in the result string. This allows us to detect when a repeating cycle starts.
   • If a remainder repeats, insert a '(' at the position where this remainder first appeared, and append a ')' at the end. This encloses the repeating part.
   • If the remainder becomes zero, there is no cycle and the division terminates.
7. Combine and Return: Join all parts together to form the final string representation.

The use of a hash map (dictionary) for remainder positions is crucial because it allows us to detect repeating cycles in O(1) time per digit, making the solution efficient.

Example Walkthrough

Let's walk through the example numerator = 2, denominator = 3:

• Step 1: Integer part: 2 / 3 = 0. So, result so far is "0".
• Step 2: Remainder: 2 % 3 = 2. Start the fractional part, add '.'.
• Step 3: Multiply remainder by 10: 2 * 10 = 20. 20 / 3 = 6, so add '6' to result ("0.6"). New remainder: 20 % 3 = 2.
• Step 4: The remainder '2' has appeared before! This means the sequence after the decimal is repeating.
• Step 5: Insert '(' at the position where remainder '2' first appeared after the decimal, and append ')'. The result becomes "0.(6)".

This process ensures that only the repeating part is inside parentheses, and the string representation is correct.

Time and Space Complexity

Brute-force Approach:

• Using floating-point division and string conversion could not detect repeating cycles and may lead to incorrect or imprecise results. It is also not feasible due to floating-point precision limitations.

• Time Complexity: O(n), where n is the length of the repeating cycle or until the remainder becomes zero. Each new remainder is processed only once.
• Space Complexity: O(n), for storing the remainder positions in the hash map. In the worst case, every remainder before repeating or terminating is unique.

This approach is efficient and avoids the pitfalls of floating-point arithmetic by simulating the division process manually.

Summary

The solution to the "Fraction to Recurring Decimal" problem involves simulating manual division and tracking remainders to detect cycles. By using a hash map to remember where each remainder first appeared, we can efficiently identify repeating decimals and correctly format the result with parentheses. The approach is both accurate and efficient, making it a robust solution for handling all edge cases, including negative numbers and repeating decimal cycles.