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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/math/fraction-to-recurring-decimal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.