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

# Fraction to Recurring Decimal

## Problem

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.

If multiple answers are possible, return **any of them**.

It is **guaranteed** that the length of the answer string is less than `10^4` for all the given inputs.

{% hint style="info" %}
For example:

```
Input: numerator = 1, denominator = 2
Output: "0.5"
```

```
Input: numerator = 2, denominator = 1
Output: "2"
```

```
Input: numerator = 2, denominator = 3
Output: "0.(6)"
```

```
Input: numerator = 4, denominator = 333
Output: "0.(012)"
```

{% endhint %}

### Thought Process

* We just have to keep track of the remainders. The moment we see a repeated one (`1700` in this example), we stop and ask "when was the first time I saw this remainder?" For this particular example, the answer is "when I was trying to find the `3rd` decimal place". Therefore, the recurrence starts from the `3rd` decimal place. That's it.

![](/files/-MQUGlC3guq_x33wleBZ)

* Using a HashMap to store remainder so that we could know if a same remainder exists

* A HashMap is the best for this question so we can detect a "cycle" with there being repeating remainders. Similar to the Happy Number problem

* (Remainder \* 10 / denominator) is what we have for fractional part

## Solution

```
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if denominator == 0:
            return 
        neg = (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0)
        res = ""
        
        if neg:
            res+="-"
        
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        if numerator % denominator == 0:
            res+=str(numerator//denominator)
            return res
        
        
        res+=str(numerator//denominator)
        res+="."
        
        r = numerator % denominator #get the initial remainder
        
        dic = {}
        
        while r:
            
            if r in dic:
                res = res[:dic[r]] + '(' + res[dic[r]:] + ')'
                print(dic)
                break
            dic[r] = len(res)
            
            r*=10
            res+=str(r//denominator) #append current decimal 
            r = r % denominator #get the next remainder
           
        
        return res
            
        
        
```

## Time Complexity

* **Time**: O(denominator) becuase the mod iteration must be less than  the denominator, so you can run from 1 to mod times
* **Space:** O(denominator)