LeetCode 166: Fraction to Recurring Decimal

Problem Restatement

We are given two integers:

numerator
denominator

They represent the fraction:

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:

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

Example function shape:

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

Examples

Example 1:

numerator = 1
denominator = 2

The fraction is:

1 / 2 = 0.5

So the answer is:

"0.5"

Example 2:

numerator = 2
denominator = 1

The fraction is an integer:

2 / 1 = 2

So the answer is:

"2"

Example 3:

numerator = 2
denominator = 3

Long division gives:

0.666666...

The digit 6 repeats forever.

So the answer is:

"0.(6)"

Example 4:

numerator = 4
denominator = 333

Long division gives:

0.012012012...

The repeating part is:

"012"

So the answer is:

"0.(012)"

First Thought: Use Floating Point

One tempting idea is:

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:

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:

2 // 3 = 0
remainder = 2

Then multiply the remainder by 10:

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:

remainder -> index in result

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

Algorithm

First handle zero:

if numerator == 0:
    return "0"

Then handle the sign.

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

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

Use absolute values for the division.

Compute the integer part:

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:

numerator = 4
denominator = 333

Integer part:

4 // 333 = 0
remainder = 4

Start result:

"0."

Now simulate decimal digits.

Now the remainder 4 appears again.

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

"0."

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

Insert parentheses:

"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:

(r * 10) // denominator

and the next remainder is:

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

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

Implementation

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:

if numerator == 0:
    return "0"

This avoids returning values like "-0".

The sign is handled before taking absolute values:

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

Then we divide using positive numbers:

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

Compute the integer part and the first remainder:

integer_part = numerator // denominator
remainder = numerator % denominator

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

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

Otherwise, add the decimal point:

result.append(".")

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

seen = {}

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

if remainder in seen:

If yes, insert parentheses:

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

If no, store its current position:

seen[remainder] = len(result)

Then generate the next digit by long division:

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

Testing

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