Fraction to Recurring Decimal
Fraction to Recurring Decimal: given two integers numerator and denominator, return the fraction as a string, with the repeating part enclosed in parentheses if it recurs.
- -2³¹ <= numerator, denominator <= 2³¹ - 1
- denominator != 0
Intuition
Fraction to recurring decimal converts a fraction to its decimal string, wrapping any repeating part in parentheses. Long division is straightforward; detecting the repeat is the actual problem.
The governing fact comes from long division itself. At each step a remainder produces a digit and a new remainder, so the sequence of digits depends entirely on the remainders:
- A remainder that appears twice produces the same digits from that point onward, so the repeat begins exactly where that remainder first occurred.
So record each remainder together with the position in the output where it was seen. When a remainder recurs, insert ( at its recorded position and ) at the end. Storing only the remainders without their positions detects that a cycle exists but not where it starts.
A remainder of 0 terminates the division exactly — that is a finite decimal with no parentheses.
Three details cause most failures:
The sign must be handled before the division and prepended afterwards, since mixing negatives into the remainder arithmetic gives inconsistent results across languages. The result is negative when exactly one operand is negative.
Overflow is real: the numerator can be −2³¹, whose absolute value exceeds the 32-bit range. Convert to a 64-bit type before taking absolute values.
And a numerator of 0 returns "0" regardless of the denominator, before any sign logic runs.
Whenever a problem asks you to convert a fraction to its decimal representation — or detect a repeating cycle in a division — the shape is long-division simulation with remainder tracking. The remainder uniquely determines the future of the division, so a repeated remainder means a repeated sequence of digits.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(d) time and O(d) space.
Handle zero and sign first
A zero numerator returns "0" immediately. Determine the sign before dividing and prepend it after — negative operands in the remainder arithmetic behave inconsistently across languages.
Guard against overflow
The numerator can be -2³¹, whose absolute value exceeds the 32-bit range. Convert to a 64-bit type before taking absolute values, or the conversion silently wraps.
Compute the integer part
Divide to get the whole-number portion and keep the remainder. If that remainder is 0, the result is exact and no decimal point is needed.
Record remainders with positions
Map each remainder to the output position where it appeared. Storing remainders alone proves a cycle exists but cannot say where it begins.
Run long division digit by digit
Multiply the remainder by 10, take the quotient as the next digit, and keep the new remainder. This is ordinary long division, one digit per step.
Close the cycle on a repeat
When a remainder recurs, insert ( at its recorded position and ) at the end. A remainder of 0 instead ends the division with a finite decimal.
Cost of the conversion
Each distinct remainder appears at most once before repeating, and there are fewer than denominator of them, giving O(denominator) time and space in the worst case.
Solution & live demo
Common pitfalls
Checking remainder before recording the digit instead of after
remainder = remainder * 10
if remainder in seen:
break
digit = remainder // denominator
remainder = remainder % denominatorremainder = remainder * 10
digit = remainder // denominator
remainder = remainder % denominator
if remainder in seen:
breakThe remainder that determines repetition is the one after extracting the digit, not before. Checking before means you detect a 'repeat' of the inflated remainder and miss the correct insertion point.
Forgetting to handle the sign with XOR logic
if numerator < 0 or denominator < 0:
result.append('-')if (numerator < 0) != (denominator < 0) and numerator != 0:
result.append('-')Using or instead of XOR makes -3 / -7 negative when it should be positive. Also, 0 should never get a minus sign, so the numerator != 0 guard is needed.
Using Python's // and % on negative numbers without taking abs first
integer_part = numerator // denominator
integer_part = abs(numerator) // abs(denominator)
Python's floor division rounds toward negative infinity, so -1 // 3 gives -1 instead of 0. Working with absolute values and handling the sign separately avoids this.
Edge cases
The result is "0" regardless of the denominator. No sign, no decimal.
The sign check adds a leading -. Using absolute values for the division avoids sign issues in the modulus operator.
In Python, integers have arbitrary precision so this is not an issue. In C++/Java, this specific case overflows INT_MAX and must be guarded — but the Python solution handles it naturally.