166. Fraction to Recurring Decimal
Asked at Goldman Sachs
Difficulty
Medium
Time
O(d)
Space
O(d)
Pattern
Hash Table
Companies
1
Problem
You are given two integers, numerator and denominator. They represent the fraction numerator / denominator. Return that fraction written as a decimal string.
If the decimal part ends (like 1/2 = 0.5), just write it out. If the decimal part repeats forever (like 4/333 = 0.012012012...), write the part that repeats once, wrapped in parentheses: "0.(012)". If the fraction is a whole number, return only the integer part, with no decimal point.
Sign rules: the result is negative only when exactly one of the two inputs is negative. A zero numerator always gives "0" with no minus sign. The answer string is guaranteed to be shorter than 10^4 characters.
What the answer looks like
Constraints
- ●
-2^31 <= numerator, denominator <= 2^31 - 1 - ●
denominator != 0 - ●
The length of the answer string is less than 10^4
Examples
numerator = 1, denominator = 2"0.5"numerator = 2, denominator = 1"2"numerator = 4, denominator = 333"0.(012)"Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Handle the sign and the integer part first: the sign is negative when exactly one input is negative, and the integer part is abs(num) // abs(den). If the remainder is 0, you are done.
Key insight: in long division, each new digit is determined entirely by the current remainder. If a remainder repeats, every digit after it repeats too. So record the position where each remainder first appeared.
Loop: multiply the remainder by 10, append rem // den as the next digit, set rem = rem % den. Before producing a digit, check the map — if rem was seen at position p, insert ( at p and append ).
Walkthrough for 4/333: integer part 0, rem 4. rem 4 at pos 0 -> 40/333 = 0, rem 40. rem 40 at pos 1 -> 400/333 = 1, rem 67. rem 67 at pos 2 -> 670/333 = 2, rem 4. rem 4 seen at pos 0 -> "0.(012)".
Edge cases: negative results like -1/2 -> "-0.5", zero numerator (no minus sign: "0"), and overflow when numerator = -2^31 and denominator = -1 in fixed-width languages — use 64-bit integers.
Optimal Approach
Step 1: If numerator == 0, return "0".
Step 2: Add - if exactly one of the inputs is negative. Work with absolute values as 64-bit integers.
Step 3: Append the integer part n // d. Let rem = n % d; if 0, return.
Step 4: Append .. Keep a map seen from remainder to index in the output.
Step 5: While rem != 0:
If rem is in seen: insert ( at seen[rem], append ), stop.
seen[rem] = len(output)
rem *= 10; append rem // d; rem %= d.
Step 6: Return the joined string.
There are at most d distinct remainders, so the loop runs at most d times.
Time: O(d). Space: O(d).
Long division with a remainder map
What Trips People Up in Real Interviews
Keying the map on the digit instead of the remainder. The same digit can appear in non-repeating positions (1/6 = 0.1(6)); only remainders determine the cycle.
Integer overflow on abs(-2147483648) in C++/Java. Cast to long before taking absolute values.
Emitting "-0" for a zero numerator with a negative denominator. Return "0" before adding a sign.
Recording the remainder after producing its digit. You must store the position before appending the digit, or the parenthesis lands one place too late.
Solution Code
O(d) timedef fractionToDecimal(numerator, denominator):
if numerator == 0:
return "0"
out = []
if (numerator < 0) != (denominator < 0):
out.append('-')
n, d = abs(numerator), abs(denominator)
out.append(str(n // d))
rem = n % d
if rem == 0:
return ''.join(out)
out.append('.')
seen = {}
while rem:
if rem in seen:
out.insert(seen[rem], '(')
out.append(')')
break
seen[rem] = len(out)
rem *= 10
out.append(str(rem // d))
rem %= d
return ''.join(out)Frequently Asked Questions
What is the Fraction to Recurring Decimal problem?
Fraction to Recurring Decimal asks you to convert `numerator / denominator` into its decimal string, wrapping a repeating fractional part in parentheses — for example `4/333` becomes `"0.(012)"`. The trick is detecting when long division starts repeating, which comes down to spotting a remainder you have seen before.
How do you solve Fraction to Recurring Decimal?
The optimal approach runs in O(d) time and O(d) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Fraction to Recurring Decimal?
Fraction to Recurring Decimal is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Fraction to Recurring Decimal?
- Keying the map on the digit instead of the remainder. The same digit can appear in non-repeating positions (`1/6 = 0.1(6)`); only remainders determine the cycle.
- Integer overflow on `abs(-2147483648)` in C++/Java. Cast to `long` before taking absolute values.
- Emitting `"-0"` for a zero numerator with a negative denominator. Return `"0"` before adding a sign.
- Recording the remainder after producing its digit. You must store the position before appending the digit, or the parenthesis lands one place too late.