# Fraction to Recurring Decimal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fraction-to-recurring-decimal)
Canonical: https://scaleengineer.com/dsa/problems/fraction-to-recurring-decimal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table, String
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [IXL](https://scaleengineer.com/companies/ixl)
---
## 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 `104` for all the given inputs.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

* `-231 <= numerator, denominator <= 231 - 1`
* `denominator != 0`

# Approaches
## Simulation with Linear Search for Remainder
This approach simulates long division and tracks the remainders to detect a repeating cycle. Instead of using an efficient data structure like a HashMap, it stores the sequence of remainders in a list. To check if a remainder has been seen before, it performs a linear search through the list. This makes the cycle detection step less efficient than a hash-based lookup.
**Time:** O(d^2) · **Space:** O(d)
**Pros:** It correctly solves the problem by tracking remainders.; The logic is a direct simulation of how one might detect cycles manually without optimized lookups.
**Cons:** The linear search for a repeated remainder is inefficient, leading to a quadratic time complexity, which can be too slow for large denominators.
### Explanation
This approach correctly solves the problem by simulating long division. The core idea is to keep track of the remainders generated at each step of the division of the fractional part. A repeating remainder signals the beginning of a repeating sequence of digits.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder res = new StringBuilder();
        if ((numerator > 0) ^ (denominator > 0)) {
            res.append("-");
        }
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
        res.append(num / den);
        long rem = num % den;
        if (rem == 0) {
            return res.toString();
        }
        res.append(".");
        
        StringBuilder fractionPart = new StringBuilder();
        List<Long> remainderList = new ArrayList<>();
        
        while (rem != 0) {
            if (remainderList.contains(rem)) {
                int startIndex = remainderList.indexOf(rem);
                res.append(fractionPart.substring(0, startIndex));
                res.append("(");
                res.append(fractionPart.substring(startIndex));
                res.append(")");
                return res.toString();
            }
            
            remainderList.add(rem);
            rem *= 10;
            fractionPart.append(rem / den);
            rem %= den;
        }
        
        res.append(fractionPart);
        return res.toString();
    }
}
```

In this implementation, we use an `ArrayList` to store the remainders. The `contains` and `indexOf` methods on an `ArrayList` both perform a linear scan, which takes O(N) time, where N is the current size of the list. Since the list can grow up to the size of the denominator, this lookup becomes the bottleneck.
### Algorithm
*   Handle the sign and integer part of the fraction as usual, using `long` to prevent overflow.
*   If there is a fractional part, initialize an `ArrayList` to store the remainders encountered during the long division process.
*   Begin a loop to calculate the digits of the fractional part.
*   In each step, before processing the current remainder, check if it already exists in the list of remainders by performing a linear scan (`list.contains(remainder)`). This check takes time proportional to the number of digits generated so far.
*   If the remainder is found, a cycle is detected. Find its index in the list (`list.indexOf(remainder)`) to determine where the repeating part starts. Format the output string with parentheses and return.
*   If the remainder is new, add it to the list, and continue the long division: multiply the remainder by 10, calculate the next digit, and find the new remainder.
*   If the remainder becomes 0, the fraction is terminating. Append the calculated fractional part and return.

## Long Division Simulation with HashMap
This is the standard and efficient approach. It mimics the manual long division process. The key insight is that if a remainder repeats during the division process, the sequence of digits generated from that point on will also repeat. We use a HashMap to store the remainders we have encountered and the position in the result string where the corresponding digit was placed. This allows for O(1) average time lookup to detect a cycle.
**Time:** O(d) · **Space:** O(d)
**Pros:** Highly efficient due to O(1) average time for cycle detection using a HashMap.; Robust and correctly identifies the start of the repeating cycle in a single pass.; It is the standard and optimal algorithm for this problem.
**Cons:** Requires extra space for the HashMap to store remainders.
### Explanation
This optimal solution simulates long division while using a `HashMap` to efficiently detect repeating remainders. A repeating remainder indicates the start of a recurring cycle in the decimal expansion.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }

        StringBuilder result = new StringBuilder();
        // Step 1: Determine the sign
        if ((numerator > 0) ^ (denominator > 0)) {
            result.append("-");
        }

        // Step 2: Use long to avoid overflow and work with absolute values
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        // Step 3: Append the integer part
        result.append(num / den);
        long remainder = num % den;

        // Step 4: If remainder is 0, we are done
        if (remainder == 0) {
            return result.toString();
        }

        // Step 5: Append the decimal point
        result.append(".");

        // Step 6: Use a map to track remainders and their positions
        Map<Long, Integer> remainderMap = new HashMap<>();
        
        // Step 7: Simulate long division for the fractional part
        while (remainder != 0) {
            // Step 8: Check for repeating remainder
            if (remainderMap.containsKey(remainder)) {
                int startIndex = remainderMap.get(remainder);
                result.insert(startIndex, "(");
                result.append(")");
                break;
            }

            // Step 9: Store the remainder and its position
            remainderMap.put(remainder, result.length());

            // Step 10: Continue long division
            remainder *= 10;
            result.append(remainder / den);
            remainder %= den;
        }

        return result.toString();
    }
}
```
By using a `HashMap`, checking for a previously seen remainder becomes an O(1) operation on average. This significantly improves the time complexity compared to a linear search, making the algorithm efficient enough to handle large denominators within the given constraints.
### Algorithm
*   Handle the trivial case where the numerator is 0.
*   Determine the sign of the result. If the numerator and denominator have opposite signs, the result is negative. Prepend a "-" to the result `StringBuilder`.
*   Convert the numerator and denominator to `long` and take their absolute values to prevent integer overflow and simplify calculations.
*   Calculate the integer part of the fraction (`num / den`) and append it to the result.
*   Calculate the initial remainder (`num % den`). If the remainder is 0, the division is exact, and we can return the result.
*   If there is a remainder, append a decimal point "." to the result.
*   Initialize a `HashMap<Long, Integer>` to store remainders as keys and their corresponding positions (indices) in the result string as values.
*   Enter a loop that continues as long as the remainder is not zero.
*   Inside the loop, check if the current remainder already exists in the HashMap. This is an O(1) average time operation.
*   If it does, a repeating cycle has been found. Retrieve the index `start` where this remainder first appeared. Insert an opening parenthesis `(` at that index in the result string and append a closing parenthesis `)` at the end. Then, break the loop.
*   If the remainder is new, add it to the HashMap with the current length of the result string as its position: `map.put(remainder, result.length())`.
*   Proceed with the long division: multiply the remainder by 10, append the integer quotient of this new number and the denominator (`remainder * 10 / den`) to the result, and update the remainder to be the new remainder (`remainder * 10 % den`).
*   Once the loop terminates (either by finding a cycle or the remainder becoming zero), return the final string from the `StringBuilder`.

# Solutions
### CSharp

```csharp
// https://leetcode.com/problems/fraction-to-recurring-decimal/ using System.Collections.Generic ; using System.Text ; public partial class Solution { public string FractionToDecimal ( int numerator , int denominator ) { var n = ( long ) numerator ; var d = ( long ) denominator ; var sb = new StringBuilder (); if ( n < 0 ) { n = - n ; if ( d < 0 ) { d = - d ; } else { sb . Append ( '-' ); } } else if ( n > 0 && d < 0 ) { d = - d ; sb . Append ( '-' ); } sb . Append ( n / d ); n = n % d ; if ( n != 0 ) { sb . Append ( '.' ); var dict = new Dictionary < long , int >(); while ( n != 0 ) { int index ; if ( dict . TryGetValue ( n , out index )) { sb . Insert ( index , '(' ); sb . Append ( ')' ); break ; } else { dict . Add ( n , sb . Length ); n *= 10 ; sb . Append ( n / d ); n %= d ; } } } return sb . ToString (); } }
```

### Java

```java
class Solution { public String fractionToDecimal ( int numerator , int denominator ) { if ( numerator == 0 ) { return "0" ; } StringBuilder sb = new StringBuilder (); boolean neg = ( numerator > 0 ) ^ ( denominator > 0 ); sb . append ( neg ? "-" : "" ); long num = Math . abs (( long ) numerator ); long d = Math . abs (( long ) denominator ); sb . append ( num / d ); num %= d ; if ( num == 0 ) { return sb . toString (); } sb . append ( "." ); Map < Long , Integer > mp = new HashMap <>(); while ( num != 0 ) { mp . put ( num , sb . length ()); num *= 10 ; sb . append ( num / d ); num %= d ; if ( mp . containsKey ( num )) { int idx = mp . get ( num ); sb . insert ( idx , "(" ); sb . append ( ")" ); break ; } } return sb . toString (); } }
```

### CPP

```cpp
using LL = long long ; class Solution { public: string fractionToDecimal ( int numerator , int denominator ) { if ( numerator == 0 ) return "0" ; string res = "" ; bool neg = ( numerator > 0 ) ^ ( denominator > 0 ); if ( neg ) res += "-" ; LL num = abs ( numerator ); LL d = abs ( denominator ); res += to_string ( num / d ); num %= d ; if ( num == 0 ) return res ; res += "." ; unordered_map < LL , int > mp ; while ( num ) { mp [ num ] = res . size (); num *= 10 ; res += to_string ( num / d ); num %= d ; if ( mp . count ( num )) { int idx = mp [ num ]; res . insert ( idx , "(" ); res += ")" ; break ; } } return res ; } };
```

### Python

```python
class Solution : def fractionToDecimal ( self , numerator : int , denominator : int ) -> str : if numerator == 0 : return '0' res = [] neg = ( numerator > 0 ) ^ ( denominator > 0 ) if neg : res . append ( '-' ) num , d = abs ( numerator ), abs ( denominator ) res . append ( str ( num // d )) num %= d if num == 0 : return '' . join ( res ) res . append ( '.' ) mp = {} while num != 0 : mp [ num ] = len ( res ) num *= 10 res . append ( str ( num // d )) num %= d if num in mp : idx = mp [ num ] res . insert ( idx , '(' ) res . append ( ')' ) break return '' . join ( res )
```