← DSA Atlas
Dedicated problem page · #166

Fraction to Recurring Decimal

MediumRandomization, Math and Miscellaneous (FAANG add-on)Long division with remainder cycle detectionHash map of seen remainders
Solve on LeetCode ↗
166
MediumRandomization, Math and Miscellaneous (FAANG add-on)Hash map of seen remaindersLong division with remainder cycle detection

Fraction to Recurring Decimal

Given two integers numerator and denominator, return the fraction as a string in decimal form. If the fractional part is repeating, enclose the repeating portion in parentheses. Any valid answer under 10^4 characters is accepted.

Open official problem prompt ↗
In plain English

Produce the exact decimal representation of a fraction, explicitly marking any infinitely repeating tail.

Picture it like this

Doing long division by hand: you keep bringing down zeros, and the moment you see a remainder you have seen before you know the digits will loop forever from that point.

Example
Input
numerator = 1, denominator = 6
Output
"0.1(6)"
Why
1/6 = 0.16666..., so the non-repeating digit 1 is followed by the repeating digit 6 in parentheses.
Constraints
-2^31 <= numerator, denominator <= 2^31 - 1denominator != 0The answer string is guaranteed to be less than 10^4 characters
Pattern lesson

See the pattern, then code

Long division with remainder cycle detection
Recognition clue

You must produce an exact decimal expansion and mark repetition; a repeating decimal appears exactly when a remainder recurs, signaling remainder-tracking long division.

↗
Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. In long division a remainder fully determines all subsequent digits, so the first time a remainder repeats the decimal starts cycling; record each remainder's output position to know where to insert the opening parenthesis.

New words, made simpleKnow these before the algorithm
Remainder
What is left after each division step; multiplied by 10 to produce the next digit.
Repeating block
The digit sequence that recurs indefinitely, wrapped in parentheses.
Sign XOR
Result is negative exactly when one operand is negative, tested with the caret operator.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Floating point formatting

Loses precision and cannot detect or bracket the repeating cycle.

Compute numerator/denominator as a float and format.

Time O(1)Space O(1)
Best choiceLong division + remainder map

Exact, and pinpoints the cycle start for the parentheses.

Simulate division digit by digit and record where each remainder first appeared.

Time O(d)Space O(d)
The rule we keep true

Invariant

Each remainder maps to the output index of the digit it produces; encountering a stored remainder means the digits from that index onward form the repeating block.

Why this is correct

Reasoning

There are at most |denominator| distinct nonzero remainders, so division either terminates (remainder hits zero) or a remainder must repeat; because a remainder deterministically generates the next digit and remainder, repetition of a remainder guarantees repetition of the entire following digit sequence.

The algorithm in three movesSay these aloud before coding
1Handle zero and the result sign via XOR of operand signs

int part 0, rem 1

2Emit the integer part and stop if the remainder is zero

rem 1 at idx 2 -> digit 1, rem 4

3Repeatedly multiply the remainder by 10, emit the quotient digit, and record the remainder's index

rem 4 at idx 3 -> digit 6, rem 4 repeats -> wrap

4When a remainder recurs, wrap the digits from its first index to now in parentheses

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
/1
62
=3
0.1(6)4
1 · Read1 / 6
2 · AskWhole part?
3 · Update stateres=['0'], rem=1
4 · ResultAppend '.' since rem != 0.
Key takeaway

Long division of 1/6 detecting the repeating remainder 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Zero case

    A zero numerator short-circuits to "0".

  2. 2
    Lines 6-7Sign handling

    XOR of the two sign tests yields a leading minus only when exactly one operand is negative.

  3. 3
    Lines 8-13Integer part

    Emit num//den; if the remainder is zero the fraction is exact and we return early.

  4. 4
    Lines 15-25Fractional loop

    Track remainder positions; on repeat, bracket the cycle.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • numerator = 0 -> "0"
  • Exact division like 1/2 -> "0.5" with no parentheses
  • Negative result such as -1/2 -> "-0.5"
  • INT_MIN numerator where abs must be handled (Python big ints make this safe)
!

Common beginner mistakes

  • Using float division and losing precision
  • Computing the sign after taking absolute values
  • Inserting the parenthesis at the wrong index by tracking digit count instead of output-string index
  • Forgetting the early return when the fraction terminates
Check your understanding

Why does a repeated remainder guarantee a repeating decimal?

More in Randomization, Math and Miscellaneous (FAANG add-on)

#43Multiply StringsSchoolbook grid multiplication#68Text JustificationGreedy line packing with space distribution#204Count PrimesSieve of Eratosthenes#273Integer to English WordsChunk-by-thousands decomposition#382Linked List Random NodeReservoir sampling (size 1)#384Shuffle an ArrayFisher-Yates shuffle