Fraction to Recurring Decimal
Asked at Goldman Sachs
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.