166. Fraction to Recurring Decimal

Explanation

To convert a fraction to a recurring decimal, we need to perform long division. The key observation is that when a remainder repeats, the decimal representation starts to repeat as well. We maintain a hashmap to keep track of the remainder and its corresponding position in the result string. If we encounter a remainder that we have seen before, it means the pattern is repeating, and we enclose the repeating part in parentheses.

Algorithm

Handle the sign of the result.
Calculate the integer part by dividing numerator by denominator.
Calculate the fractional part using long division.
Keep track of remainders and their positions in the result.
If a remainder repeats, enclose the repeating part in parentheses.
Construct the final string.

Time Complexity

The time complexity of this algorithm is O(n), where n is the maximum number of digits in the result.

Space Complexity

The space complexity is O(n) to store the remainders and their positions.

View Leetcode Problem

import java.util.HashMap;

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

        StringBuilder result = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) {
            result.append("-");
        }

        long num = Math.abs((long) numerator);
        long denom = Math.abs((long) denominator);

        // Integer part
        result.append(num / denom);
        num %= denom;
        if (num == 0) {
            return result.toString();
        }

        // Fractional part
        result.append(".");
        HashMap<Long, Integer> map = new HashMap<>();
        map.put(num, result.length());

        while (num != 0) {
            num *= 10;
            result.append(num / denom);
            num %= denom;

            if (map.containsKey(num)) {
                int index = map.get(num);
                result.insert(index, "(");
                result.append(")");
                break;
            } else {
                map.put(num, result.length());
            }
        }

        return result.toString();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.