Fraction to Recurring Decimal
Medium · Math & Geometry · Explanation and code example
Long Division with Remainder Positions
How it works
Long division produces the next digit from the current remainder. If the same remainder appears again, every following division step repeats. Store the output position of each remainder so the repeated part can be enclosed in parentheses.
Steps
- Determine the sign and emit the integer part.
- Map each remainder to its digit position before multiplying it by ten.
- Generate digits until the remainder is zero or repeats, then mark the cycle.
Complexity
- Time: O(L) for L generated digits, using amortized string/list appends.
- Space: O(L) for remainder positions and output.
Things to watch for
- Promote signed integers before taking an absolute value in C++.
- Store the remainder position before generating its digit.
- Zero numerator returns
0, with no negative sign.
Python code example
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
sign = "-" if (numerator < 0) != (denominator < 0) else ""
numerator, denominator = abs(numerator), abs(denominator)
integer, remainder = divmod(numerator, denominator)
prefix = sign + str(integer)
if remainder == 0:
return prefix
positions, digits = {}, []
while remainder and remainder not in positions:
positions[remainder] = len(digits)
digit, remainder = divmod(remainder * 10, denominator)
digits.append(str(digit))
if remainder:
start = positions[remainder]
digits.insert(start, "(")
digits.append(")")
return prefix + "." + "".join(digits)
C++ code example
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0)
return "0";
string ans;
if (numerator < 0 ^ denominator < 0)
ans += "-";
long n = labs(numerator);
long d = labs(denominator);
ans += to_string(n / d);
if (n % d == 0)
return ans;
ans += '.';
unordered_map<int, int> seen;
for (long r = n % d; r; r %= d) {
if (const auto it = seen.find(r); it != seen.cend()) {
ans.insert(it->second, 1, '(');
ans += ')';
break;
}
seen[r] = ans.size();
r *= 10;
ans += to_string(r / d);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.