Fraction to Recurring Decimal
Fraction to Recurring Decimal is a medium arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (hash map from remainder to position), runs in O(L) time and O(L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of remainders, linear search) up.
Problem
Given two integers numerator and denominator, return their quotient written as a decimal string.
If the digits after the decimal point repeat forever, write the repeating block once and wrap it in parentheses, for example 1/3 becomes "0.(3)". If the division ends, write it without parentheses, and write a whole-number result without a decimal point. A negative result starts with -.
Place the opening parenthesis as early as possible and keep the repeating block as short as possible (so 1/6 is "0.1(6)", not "0.1(66)"). The inputs are such that the answer is shorter than 10^4 characters.
Examples
Example 1
- Input
numerator = 7, denominator = 8- Output
"0.875"- Why
- The division ends after three decimal digits.
Example 2
- Input
numerator = 5, denominator = 6- Output
"0.8(3)"- Why
- 5 / 6 = 0.8333…; the digit 3 repeats forever, so it goes in parentheses.
Example 3
- Input
numerator = -50, denominator = 22- Output
"-2.(27)"- Why
- 50 / 22 = 2.272727…, the block "27" repeats, and the result is negative.
Constraints
-2^31 <= numerator, denominator <= 2^31 - 1denominator != 0- The answer string is shorter than
10^4characters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list of remainders, linear search) | O(L²) | O(L) |
| Optimal (hash map from remainder to position) | O(L) | O(L) |
1Brute force (list of remainders, linear search)
O(L²)For each of the L fraction digits the list of earlier remainders is scanned.O(L)The list of remainders and the output.Do long division and keep every remainder in a list in the order it appeared. Before producing the next digit, search the list for the current remainder; if it is there, the digits from that index on repeat.
- Handle the sign and work with absolute values as 64-bit numbers.
- Write the integer part; if the remainder is 0, stop.
- Loop: search
seenfor rem; if found at index k, wrap the fraction digits from k onward in parentheses and stop. - Otherwise add rem to
seen, rem *= 10, append rem / den, rem %= den; stop when rem becomes 0.
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
StringBuilder sb = new StringBuilder();
if ((numerator < 0) ^ (denominator < 0)) sb.append('-');
long num = Math.abs((long) numerator), den = Math.abs((long) denominator);
sb.append(num / den);
long rem = num % den;
if (rem == 0) return sb.toString();
sb.append('.');
List<Long> seen = new ArrayList<>();
StringBuilder frac = new StringBuilder();
while (rem != 0) {
int k = seen.indexOf(rem);
if (k >= 0) {
frac.insert(k, '(').append(')');
break;
}
seen.add(rem);
rem *= 10;
frac.append(rem / den);
rem %= den;
}
return sb.append(frac).toString();
}
}class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
sign = "-" if (numerator < 0) != (denominator < 0) else ""
num, den = abs(numerator), abs(denominator)
head = sign + str(num // den)
rem = num % den
if rem == 0:
return head
seen = []
frac = []
while rem != 0:
if rem in seen:
k = seen.index(rem)
return head + "." + "".join(frac[:k]) + "(" + "".join(frac[k:]) + ")"
seen.append(rem)
rem *= 10
frac.append(str(rem // den))
rem %= den
return head + "." + "".join(frac)class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
string res;
if ((numerator < 0) ^ (denominator < 0)) res += '-';
long long num = llabs((long long)numerator), den = llabs((long long)denominator);
res += to_string(num / den);
long long rem = num % den;
if (rem == 0) return res;
res += '.';
vector<long long> seen;
string frac;
while (rem != 0) {
auto it = find(seen.begin(), seen.end(), rem);
if (it != seen.end()) {
int k = it - seen.begin();
frac.insert(k, "(");
frac += ')';
break;
}
seen.push_back(rem);
rem *= 10;
frac += char('0' + rem / den);
rem %= den;
}
return res + frac;
}
};function fractionToDecimal(numerator, denominator) {
if (numerator === 0) return "0";
const sign = (numerator < 0) !== (denominator < 0) ? "-" : "";
const num = Math.abs(numerator), den = Math.abs(denominator);
const head = sign + Math.floor(num / den);
let rem = num % den;
if (rem === 0) return head;
const seen = [];
const frac = [];
while (rem !== 0) {
const k = seen.indexOf(rem);
if (k >= 0) return head + "." + frac.slice(0, k).join("") + "(" + frac.slice(k).join("") + ")";
seen.push(rem);
rem *= 10;
frac.push(Math.floor(rem / den));
rem %= den;
}
return head + "." + frac.join("");
}2Optimal (hash map from remainder to position)
O(L)Each fraction digit costs O(1) expected time; L is bounded by the denominator and by the answer length limit.O(L)One map entry per distinct remainder, plus the output.Same long division, but store each remainder in a hash map together with the index in the output where its digit is about to be written. Detecting a repeat becomes an O(1) lookup, and the stored index is exactly where the ( goes.
- Write the sign and integer part using 64-bit absolute values; return if the remainder is 0.
- Append '.'; while rem != 0: if rem is in the map, insert '(' at map[rem], append ')', stop.
- Else map[rem] = current output length; rem *= 10; append rem / den; rem %= den.
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
StringBuilder sb = new StringBuilder();
if ((numerator < 0) ^ (denominator < 0)) sb.append('-');
long num = Math.abs((long) numerator), den = Math.abs((long) denominator);
sb.append(num / den);
long rem = num % den;
if (rem == 0) return sb.toString();
sb.append('.');
Map<Long, Integer> pos = new HashMap<>();
while (rem != 0) {
Integer at = pos.get(rem);
if (at != null) {
sb.insert((int) at, '(').append(')');
break;
}
pos.put(rem, sb.length());
rem *= 10;
sb.append(rem / den);
rem %= den;
}
return sb.toString();
}
}class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
out = []
if (numerator < 0) != (denominator < 0):
out.append("-")
num, den = abs(numerator), abs(denominator)
out.append(str(num // den))
rem = num % den
if rem == 0:
return "".join(out)
out.append(".")
pos = {}
while rem != 0:
if rem in pos:
out.insert(pos[rem], "(")
out.append(")")
break
pos[rem] = len(out)
rem *= 10
out.append(str(rem // den))
rem %= den
return "".join(out)class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
string res;
if ((numerator < 0) ^ (denominator < 0)) res += '-';
long long num = llabs((long long)numerator), den = llabs((long long)denominator);
res += to_string(num / den);
long long rem = num % den;
if (rem == 0) return res;
res += '.';
unordered_map<long long, int> pos;
while (rem != 0) {
auto it = pos.find(rem);
if (it != pos.end()) {
res.insert(it->second, "(");
res += ')';
break;
}
pos[rem] = res.size();
rem *= 10;
res += char('0' + rem / den);
rem %= den;
}
return res;
}
};function fractionToDecimal(numerator, denominator) {
if (numerator === 0) return "0";
const out = [];
if ((numerator < 0) !== (denominator < 0)) out.push("-");
const num = Math.abs(numerator), den = Math.abs(denominator);
out.push(String(Math.floor(num / den)));
let rem = num % den;
if (rem === 0) return out.join("");
out.push(".");
const pos = new Map();
while (rem !== 0) {
if (pos.has(rem)) {
out.splice(pos.get(rem), 0, "(");
out.push(")");
break;
}
pos.set(rem, out.length);
rem *= 10;
out.push(String(Math.floor(rem / den)));
rem %= den;
}
return out.join("");
}Edge cases to test
- Numerator 0 (answer "0", no sign)
- Exact integer results (no decimal point)
- Exactly one negative operand
-2^31as numerator or denominator, whose absolute value overflows a 32-bit int- A repeating block that starts right after the decimal point
Hints
Hint 1
Do long division by hand: at each step multiply the remainder by 10 and divide again.
Hint 2
The digits start repeating exactly when a remainder you have already seen comes back.
Hint 3
Remember, for each remainder, the index in the output where its digit was written, so you know where to place (.
FAQ
What is the best time complexity for Fraction to Recurring Decimal?
Optimal (hash map from remainder to position) runs in O(L) time and O(L) extra space. Each fraction digit costs O(1) expected time; L is bounded by the denominator and by the answer length limit.
Which pattern does Fraction to Recurring Decimal use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Fraction to Recurring Decimal?
Yes. Brute force (list of remainders, linear search) takes O(L²) time and O(L) space. Do long division and keep every remainder in a list in the order it appeared.
Which edge cases should I test for Fraction to Recurring Decimal?
Numerator 0 (answer "0", no sign); Exact integer results (no decimal point); Exactly one negative operand; -2^31 as numerator or denominator, whose absolute value overflows a 32-bit int; A repeating block that starts right after the decimal point.