166. Fraction to Recurring Decimal

Problem¶

Convert a fraction numerator / denominator into its decimal string.

• If the decimal terminates, return it normally.
• If digits repeat forever, wrap the repeating part in parentheses.
• Keep the sign correct.

Example:

4 / 333 -> "0.(012)"

Key trick¶

Track each remainder's first position in the output.

• In long division, the decimal starts repeating exactly when a remainder repeats.
• When that happens, insert ( at the first position where that remainder appeared, and append ) at the end.

Trap¶

• Forgetting sign handling when one value is negative.
• Not returning just the integer part when remainder is 0.
• Tracking digits instead of remainders.
• Mishandling cases like -1 / -2, 0 / 5, or 1 / 6.

Why is it interesting?¶

It turns manual long division into code.

• It tests hash map usage, edge cases, and careful string construction.
• The repeating-cycle idea is simple but easy to miss.

Python solution¶

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        a, b = numerator, denominator

        # Zero is a special case: no sign, no fractional part.
        if a == 0:
            return "0"

        parts = []

        if (a < 0) != (b < 0):
            parts.append("-")

        a = abs(a)
        b = abs(b)

        # Integer part.
        int_part, rem = divmod(a, b)
        parts.append(str(int_part))

        # No fractional part.
        if rem == 0:
            return "".join(parts)

        parts.append(".")

        # rem -> index in parts where its digit starts
        seen = {}

        while rem:
            # If this remainder was seen before, digits from that point repeat.
            if rem in seen:
                repeat_idx = seen[rem]
                parts.insert(repeat_idx, "(")
                parts.append(")")
                break

            # Record where the next digit produced by this remainder will go.
            seen[rem] = len(parts)

            rem *= 10
            digit, rem = divmod(rem, b)
            parts.append(str(digit))

        return "".join(parts)

Comment on my solution¶

Not provided.

Extra¶

Mathematical background to understand the algorithm¶

The code is clear but I've no clue why it works.

Why this:

Track each remainder's first position in the output.

• In long division, the decimal starts repeating exactly when a remainder repeats.

• Give me the necessary mathematical background to understand what's going on. Use mathematical notation.
• And go through the algo for the following case:
• (4, 333, "0.(012)")
• (1, 6, "0.1(6)")
• (50, 8, "6.25")

Think of the decimal part as long division driven only by the remainder.

For a fraction \(\dfrac{n}{d}\), after removing the integer part, let

with \(0 \le r_0 < d\).

Each decimal digit is produced by this recurrence:

where:

• \(a_{k+1}\) is the next decimal digit
• \(r_{k+1}\) is the new remainder
• equivalently,

So the whole fractional expansion is determined by repeatedly applying:

and outputting the corresponding digit.

Why repeating a remainder means repeating digits¶

The key fact is:

• if the same remainder appears again, everything after it repeats identically.

Why?

• The next digit depends only on the current remainder.
• The remainder after that also depends only on the current remainder.

So if \(r_i = r_j\) for some \(i < j\), then:

and then again:

and so on forever. Thus the block from position \(i+1\) to \(j\) repeats.

This is exactly why we store:

• each remainder
• the position in the output where its digit starts

When a remainder comes back, we know where the repeating block began.

Why a remainder must eventually repeat or become \(0\)¶

All remainders satisfy:

So there are only finitely many possible remainders:

Therefore during long division:

• either some remainder becomes \(0\), and the decimal terminates
• or some nonzero remainder repeats, and the decimal becomes periodic

This is just the pigeonhole principle.

Why remainder \(0\) means terminating decimal¶

If at some step \(r_k = 0\), then

so every future digit is \(0\), and long division stops. That means the decimal is finite.

Example 1: \(\dfrac{4}{333} = 0.(012)\)¶

Integer part:

so start with:

0.

Initial remainder:

Now iterate.

Step 1¶

Output digit: 0

Current decimal:

0.0

Store that remainder 4 produced the digit at this position.

Step 2¶

Output digit: 1

Current decimal:

0.01

Step 3¶

Output digit: 2

Current decimal:

0.012

Now the new remainder is again:

So we are back to exactly the same state as at the start. Therefore the same digits will repeat:

• from remainder \(4\) we got digit 0
• then remainder \(40\) gave 1
• then remainder \(67\) gave 2
• then back to remainder \(4\)

So the repeating block is 012:

0.(012)

A compact state table:

Example 2: \(\dfrac{1}{6} = 0.1(6)\)¶

Integer part:

Start:

0.

Initial remainder:

Step 1¶

Output digit: 1

Current decimal:

0.1

Step 2¶

Output digit: 6

Current decimal:

0.16

Now:

So from this point we are in a loop. The repeating block starts where remainder 4 first appeared, which is just before digit 6.

Hence:

0.1(6)

State view:

So after the first digit 1, we keep repeating 6.

Example 3: \(\dfrac{50}{8} = 6.25\)¶

Integer part:

Remainder:

Start:

6.

Step 1¶

Output digit: 2

Current decimal:

6.2

Step 2¶

Output digit: 5

Current decimal:

6.25

Now the remainder is \(0\), so division ends. No repetition.

How this maps to the code¶

Suppose during fractional-digit generation you have remainder r.

The code does this:

remainder *= 10
digit, remainder = divmod(remainder, denominator)

That is exactly:

The dictionary:

seen[remainder] = position

means:

• "if this remainder ever appears again, the repeating part starts at this output position"

That works because:

• a remainder is the full state of the long division
• same state implies same future
• so same remainder implies repeating suffix

The whole idea is really just:

Finite deterministic process means:

• hit \(0\) and stop
• or enter a cycle

That cycle is the repeating decimal part.

Naming clarification¶

Just a naming clarification: Does "long division" has a rigourous definition or it is just a division?

"Long division" is usually the name of the standard written algorithm for division, not a different mathematical operation.

• The operation is just division.
• "Long division" means the step-by-step procedure used to compute:
  • the integer quotient
  • the remainder
  • and, if continued, the decimal expansion

So in this problem:

• mathematically, you are computing \(\dfrac{n}{d}\)
• algorithmically, you are simulating long division

It is not usually a fully rigorous formal term in math like "group" or "field".

It is more:

• a standard school algorithm
• a conventional name in arithmetic and education

In a more rigorous/algebraic description, you would say something like:

• apply the division algorithm repeatedly
• at each step compute quotient digit and remainder

using the fact that for integers \(a\) and \(d > 0\), there exist unique integers \(q, r\) such that

That theorem is the rigorous backbone.

So short answer:

• "division" is the math operation
• "long division" is the usual manual algorithm for carrying it out digit by digit

I'm French. What is the French name for "Long division" algorithm?

The usual French name is:

• la division posée

Sometimes you may also hear:

• la division euclidienne posée for integer division with quotient and remainder
• la technique de la division posée

For decimals, in school context, division posée is the natural translation of "long division".

So here the best translation is:

• algorithme de la division posée

About the recurrence formula¶

• How did you come up with this recurrence formula \(10r_k = d \cdot a_{k+1} + r_{k+1}\)? I don't get why this produce the decimal digit series.
• How do you prove it?

Still not clear to me.

Let

and suppose for simplicity that \(n,d>0\). The sign changes nothing.

The confusion usually comes from this point:

• a decimal expansion is not magic
• each next decimal digit is obtained by isolating the current fractional remainder, multiplying it by \(10\), and dividing again

I will build the formula from scratch.

Start from Euclidean division¶

First do the usual integer division:

So

Here:

• \(q_0\) is the integer part
• \(\dfrac{r_0}{d}\) is the fractional part left to expand

So the whole problem is now:

• how do we write \(\dfrac{r_0}{d}\) in decimal?

Why multiply by \(10\)?¶

Because decimal digits are powers of \(10\).

If

then

Multiplying by \(10\) shifts the decimal point one place to the right.

So the first digit after the decimal point is exactly the integer part of

That is why we divide \(10r_0\) by \(d\).

Deriving the recurrence¶

Now apply Euclidean division again, this time to \(10r_0\):

Divide by \(d\):

Then divide by \(10\):

This already says:

• the first decimal digit is \(a_1\)
• what remains afterward is controlled by \(r_1\)

Repeat the same step on \(10r_1\):

Then

Substitute into the previous expression:

Continue forever. After \(m\) steps:

This formula is the rigorous reason the digits \(a_1,a_2,\dots\) are the decimal digits of \(\dfrac{r_0}{d}\).

The recurrence in general form¶

At step \(k\), divide \(10r_k\) by \(d\):

This is just Euclidean division.

So automatically:

and

That is where the recurrence comes from.

It is not invented. It is simply:

• "take the current remainder"
• "shift one decimal place"
• "divide by \(d\) again"

Why does \(a_{k+1}\) have to be a decimal digit?¶

Because \(0 \le r_k < d\), so

Hence

So each \(a_{k+1}\) is one of

which is exactly a decimal digit.

This is important: the recurrence is not producing arbitrary integers. It really produces decimal digits.

Why this gives the decimal expansion¶

Suppose after the integer part \(q_0\), you generate digits \(a_1,a_2,\dots\) by the recurrence.

Then for every \(m \ge 1\):

And since \(0 \le r_m < d\),

So after taking the first \(m\) digits, the error is less than \(10^{-m}\).

That is exactly what it means for

to be the decimal expansion of \(\dfrac{n}{d}\).

So this is the proof.

A concrete proof on \(\frac{1}{6}\)¶

Start with

So

Now divide \(10\cdot 1\) by \(6\):

So

Divide by \(10\):

So the first decimal digit is \(1\).

Now divide \(10\cdot 4\) by \(6\):

So

Divide by \(10\):

Substitute into the previous line:

Again, the same remainder \(4\) comes back, so the same digit \(6\) comes back forever.

Thus:

and written with repetition:

Intuition in one sentence¶

The remainder is "what is still left to convert into decimal", and multiplying it by \(10\) exposes the next decimal digit.

The shortest possible mental model¶

At any step, suppose the fraction still left is

Then:

1. Multiply by \(10\) to shift the next decimal digit into the integer part.
2. Extract that integer part:

1. Keep the new remainder:

That leftover fraction is then

waiting for the next digit.

So the process naturally repeats.