LeetCode 166: Fraction to Recurring Decimal Solution

Master LeetCode problem 166 (Fraction to Recurring Decimal), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

166. Fraction to Recurring Decimal

Medium

Hash Table Math String

Problem Explanation

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.

Solution Code

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();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 166 (Fraction to Recurring Decimal)?

This page provides optimized solutions for LeetCode problem 166 (Fraction to Recurring Decimal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 166 (Fraction to Recurring Decimal)?

The time complexity for LeetCode 166 (Fraction to Recurring Decimal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 166 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 166 in Java, C++, or Python.

Back to LeetCode Solutions