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.
Intuition
Long division by hand already tells you everything. You divide, get a quotient digit, and carry the remainder forward — multiplied by 10 — as the new dividend. A decimal repeats exactly when you see a remainder you have seen before, because from that point the same sequence of divisions will replay. So the algorithm is: do long division step by step, record each remainder and the position in the result string where it appeared, and the moment a remainder repeats, insert parentheses around the substring from its first occurrence to the current position.
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
Handle the sign and integer part separately
If exactly one of numerator or denominator is negative, the result is negative — prepend a minus sign. Work with absolute values from here. Compute the integer part with abs(numerator) // abs(denominator) and the initial remainder with abs(numerator) % abs(denominator). If the remainder is zero, there is no decimal part — return the integer as a string.
Simulate long division, tracking remainders
Append a dot and enter a loop. At each step, multiply the remainder by 10, divide by the denominator to get the next digit, and compute the new remainder. Before recording the digit, check whether this remainder has been seen before. Use a hash map from remainder to the index in the result string where it first appeared.
Insert parentheses when a remainder repeats
If the remainder appears in the map, the digits from that stored index to the current position are the repeating block. Insert ( at the stored index and ) at the end. If the remainder reaches zero, the decimal terminates — no parentheses. Time is O(d) where d is the number of distinct remainders, which is at most denominator. Space is O(d) for the map.
Solution
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.