> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/166-fraction-to-recurring-decimal.md).

# 166 Fraction to Recurring Decimal

## 166. [Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/description/)

## 1. Question

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

* Given numerator = 1, denominator = 2, return "0.5".
* Given numerator = 2, denominator = 1, return "2".
* Given numerator = 2, denominator = 3, return "0.(6)".

## 2. Implementation

**(1) Hash Table**

```java
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0 || denominator == 1) {
            return String.valueOf(numerator);
        }

        StringBuilder res = new StringBuilder();
        if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
            res.append("-");
        }

        long dividend = Math.abs((long)numerator);
        long divisor = Math.abs((long)denominator);

        //Integer Part
        res.append(dividend / divisor);
        dividend %= divisor;

        if (dividend == 0) {
            return res.toString();
        }

        // Fration Part
        res.append(".");
        Map<Long, Integer> map = new HashMap<>();

        while (dividend != 0) {
            if (map.containsKey(dividend)) {
                int index = map.get(dividend);
                res.insert(index, "(");
                res.append(")");
                break;
            }
            map.put(dividend, res.length());
            dividend *= 10;
            res.append(dividend / divisor);
            dividend %= divisor;
        }
        return res.toString();
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), n为结果的长度, 空间复杂度O(n)