---
description: (This can be classified under Hash Table too)
---

# 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.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQTICxPHseIkTNBe3Af%2F-MQUGlC3guq_x33wleBZ%2FIMG_041EF9A3C736-1.jpeg?alt=media\&token=30cde009-4ffb-4278-bc74-0c19a2bf0179)

*   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)
