# LeetCode 166: Fraction to Recurring Decimal

## Problem Restatement

We are given two integers:

```python
numerator
denominator
```

They represent the fraction:

```python
numerator / denominator
```

We need to return the decimal representation as a string.

If the fractional part repeats forever, we put the repeating part inside parentheses.

For example:

```python
1 / 2 = "0.5"
2 / 1 = "2"
2 / 3 = "0.(6)"
4 / 333 = "0.(012)"
```

The denominator is never zero, and the result string is guaranteed to have length less than `10^4`. The input values are in the 32-bit signed integer range.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `numerator` and integer `denominator` |
| Output | Decimal string representation |
| Repeating decimal | Put repeating digits inside parentheses |
| Zero denominator | Cannot happen |
| Multiple valid answers | Any valid representation is accepted |

Example function shape:

```python
def fractionToDecimal(numerator: int, denominator: int) -> str:
    ...
```

## Examples

Example 1:

```python
numerator = 1
denominator = 2
```

The fraction is:

```python
1 / 2 = 0.5
```

So the answer is:

```python
"0.5"
```

Example 2:

```python
numerator = 2
denominator = 1
```

The fraction is an integer:

```python
2 / 1 = 2
```

So the answer is:

```python
"2"
```

Example 3:

```python
numerator = 2
denominator = 3
```

Long division gives:

```python
0.666666...
```

The digit `6` repeats forever.

So the answer is:

```python
"0.(6)"
```

Example 4:

```python
numerator = 4
denominator = 333
```

Long division gives:

```python
0.012012012...
```

The repeating part is:

```python
"012"
```

So the answer is:

```python
"0.(012)"
```

## First Thought: Use Floating Point

One tempting idea is:

```python
str(numerator / denominator)
```

This fails for this problem.

Floating-point values have limited precision. They cannot reliably show long repeating patterns.

For example, `2 / 3` may become something like:

```python
0.6666666666666666
```

That does not tell us where the repetition begins.

We need exact arithmetic.

## Key Insight

Use long division.

When doing decimal division by hand, the next digit depends only on the current remainder.

For example, for `2 / 3`:

```python
2 // 3 = 0
remainder = 2
```

Then multiply the remainder by `10`:

```python
20 // 3 = 6
remainder = 2
```

The same remainder `2` appears again.

That means the same digit sequence will repeat forever.

So the rule is:

If a remainder appears twice, the decimal digits between the first occurrence and the second occurrence are repeating.

We store:

```python
remainder -> index in result
```

When a remainder repeats, insert `"("` at its first index and append `")"` at the end.

## Algorithm

First handle zero:

```python
if numerator == 0:
    return "0"
```

Then handle the sign.

The result is negative if exactly one of `numerator` or `denominator` is negative:

```python
(numerator < 0) != (denominator < 0)
```

Use absolute values for the division.

Compute the integer part:

```python
integer_part = numerator // denominator
remainder = numerator % denominator
```

If the remainder is `0`, return the integer part.

Otherwise, append `"."` and simulate long division.

For every remainder:

1. If this remainder has appeared before, insert parentheses and return.
2. Store this remainder’s current result index.
3. Multiply the remainder by `10`.
4. Append the next digit.
5. Update the remainder.

## Walkthrough

Use:

```python
numerator = 4
denominator = 333
```

Integer part:

```python
4 // 333 = 0
remainder = 4
```

Start result:

```python
"0."
```

Now simulate decimal digits.

| Remainder | Multiply by 10 | Digit | New remainder | Result |
|---:|---:|---:|---:|---|
| `4` | `40` | `0` | `40` | `"0.0"` |
| `40` | `400` | `1` | `67` | `"0.01"` |
| `67` | `670` | `2` | `4` | `"0.012"` |

Now the remainder `4` appears again.

The first time remainder `4` appeared, the result index was right after:

```python
"0."
```

So the repeating part starts at `"0"` in the fractional part.

Insert parentheses:

```python
"0.(012)"
```

## Correctness

The integer part is computed by integer division, so it is exactly the part before the decimal point.

For the fractional part, long division always uses the current remainder to determine the next digit. If the current remainder is `r`, then the next digit is:

```python
(r * 10) // denominator
```

and the next remainder is:

```python
(r * 10) % denominator
```

Therefore, if the same remainder appears again, all future digits will repeat from the earlier occurrence.

The algorithm stores the result index where each remainder first appears. When a repeated remainder is found, it inserts the opening parenthesis at exactly that index and appends the closing parenthesis at the end. This marks precisely the repeating block.

If the remainder becomes `0`, the decimal terminates, and the algorithm returns the finite decimal representation.

The sign is handled before division, and the division itself uses absolute values. Therefore, the returned string has the correct sign, integer part, finite fractional part, and repeating fractional part.

## Complexity

Let `L` be the length of the output string.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | Each decimal digit is generated once |
| Space | `O(L)` | We store result characters and seen remainders |

The problem guarantees the answer length is less than `10^4`.

## Implementation

```python
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        result = []

        if (numerator < 0) != (denominator < 0):
            result.append("-")

        numerator = abs(numerator)
        denominator = abs(denominator)

        integer_part = numerator // denominator
        remainder = numerator % denominator

        result.append(str(integer_part))

        if remainder == 0:
            return "".join(result)

        result.append(".")

        seen = {}

        while remainder != 0:
            if remainder in seen:
                start = seen[remainder]
                result.insert(start, "(")
                result.append(")")
                break

            seen[remainder] = len(result)

            remainder *= 10
            digit = remainder // denominator
            result.append(str(digit))
            remainder %= denominator

        return "".join(result)
```

## Code Explanation

The zero case returns immediately:

```python
if numerator == 0:
    return "0"
```

This avoids returning values like `"-0"`.

The sign is handled before taking absolute values:

```python
if (numerator < 0) != (denominator < 0):
    result.append("-")
```

Then we divide using positive numbers:

```python
numerator = abs(numerator)
denominator = abs(denominator)
```

Compute the integer part and the first remainder:

```python
integer_part = numerator // denominator
remainder = numerator % denominator
```

If the remainder is zero, the answer has no decimal part:

```python
if remainder == 0:
    return "".join(result)
```

Otherwise, add the decimal point:

```python
result.append(".")
```

The dictionary maps each remainder to the position where its decimal digits begin:

```python
seen = {}
```

Before generating a digit, check whether this remainder has appeared before:

```python
if remainder in seen:
```

If yes, insert parentheses:

```python
start = seen[remainder]
result.insert(start, "(")
result.append(")")
```

If no, store its current position:

```python
seen[remainder] = len(result)
```

Then generate the next digit by long division:

```python
remainder *= 10
digit = remainder // denominator
result.append(str(digit))
remainder %= denominator
```

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.fractionToDecimal(1, 2) == "0.5"
    assert sol.fractionToDecimal(2, 1) == "2"
    assert sol.fractionToDecimal(2, 3) == "0.(6)"
    assert sol.fractionToDecimal(4, 333) == "0.(012)"
    assert sol.fractionToDecimal(1, 6) == "0.1(6)"
    assert sol.fractionToDecimal(0, 7) == "0"
    assert sol.fractionToDecimal(-50, 8) == "-6.25"
    assert sol.fractionToDecimal(7, -12) == "-0.58(3)"
    assert sol.fractionToDecimal(-1, -2) == "0.5"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1 / 2` | Finite decimal |
| `2 / 1` | Integer result |
| `2 / 3` | One-digit repeating decimal |
| `4 / 333` | Multi-digit repeating decimal |
| `1 / 6` | Non-repeating prefix before repeating part |
| `0 / 7` | Zero numerator |
| `-50 / 8` | Negative finite decimal |
| `7 / -12` | Negative repeating decimal |
| `-1 / -2` | Positive result from two negatives |