Fraction to Recurring Decimal — Problem & Solution
Fraction to Recurring Decimal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Fraction to Recurring Decimal is a medium coding problem on strings, hash table and math, asked in Amazon, Google, Meta and Rubrik interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Math
- Asked at: Amazon, Google, Meta, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integers numerator and denominator, return the value of the fraction numerator / denominator written in decimal.
- If the decimal expansion terminates, write it in full with no trailing zeros (
-50 / 8is-6.25;4 / 2is2). - If it repeats, put the shortest repeating block, starting as early as possible, in parentheses (
1 / 6is0.1(6), not0.(16)or0.16(6)). - A negative value starts with
-; zero is written0.
Example 1
Input: numerator = 1, denominator = 6
Output: "0.1(6)"
Example 2
Input: numerator = -50, denominator = 8
Output: "-6.25"
Example 3
Input: numerator = 22, denominator = 7
Output: "3.(142857)"
Constraints
-2^31 <= numerator, denominator <= 2^31 - 1denominator != 0The answer string is shorter than 10^4 characters for every test
Hints for Fraction to Recurring Decimal
Hint 1
Do the long division you learned at school: the integer part first, then one digit at a time, multiplying the remainder by 10 each step.
Hint 2
The digits start repeating exactly when a remainder repeats — the next digits are determined by the remainder alone.
Hint 3
Store, for every remainder, the position in the output where its digit was written. When a remainder shows up again, insert
(at that position and append). Work with absolute values in 64-bit and put the sign in front yourself.
How to solve Fraction to Recurring Decimal
Each step of long division depends only on the current remainder, and there are fewer than |denominator| possible remainders. So the expansion either reaches remainder 0 (terminates) or revisits a remainder, and the digits produced since its first visit form the shortest earliest repeating block.
Approach
- If
numerator == 0, return0. Otherwise write-if exactly one of the inputs is negative. - Switch to 64-bit absolute values
nandd(because|-2^31|does not fit in 32 bits). Appendn / d; letr = n % d. Ifr == 0, return. - Append
.. Whiler != 0: ifrwas seen before at output positionp, insert(atp, append)and stop; otherwise rememberr → current length, setr *= 10, append the digitr / d, and setr %= d. - Return the built string.
Why it works
The fractional digits follow r_{k+1} = 10 · r_k mod d and digit 10 · r_k / d. Once some remainder repeats, the whole sequence of later digits repeats with it, so the block between the two visits repeats forever. It starts at the first remainder that recurs, which is the earliest possible start, and its length is the period of the remainder sequence, which is the shortest possible repeating block.
Complexity
- Time —
O(length of the answer) - Space —
O(length of the answer)
Pitfalls
-2147483648 / -1andabs(-2147483648)overflow 32-bit integers — convert to 64-bit first.0 / -5is0, not-0.- Detect repetition by remainders, not by digits — the same digit can come from different remainders.
Reference solution
Python
def fractionToDecimal(numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
sign = "-" if (numerator < 0) != (denominator < 0) else ""
num, den = abs(numerator), abs(denominator)
whole, rem = divmod(num, den)
if rem == 0:
return sign + str(whole)
digits = []
seen = {}
while rem != 0:
if rem in seen:
at = seen[rem]
return sign + str(whole) + "." + "".join(digits[:at]) + "(" + "".join(digits[at:]) + ")"
seen[rem] = len(digits)
rem *= 10
digits.append(str(rem // den))
rem %= den
return sign + str(whole) + "." + "".join(digits)Java
public static 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> seen = new HashMap<>();
while (rem != 0) {
Integer at = seen.get(rem);
if (at != null) {
sb.insert((int) at, "(");
sb.append(')');
break;
}
seen.put(rem, sb.length());
rem *= 10;
sb.append(rem / den);
rem %= den;
}
return sb.toString();
}C++
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> seen;
while (rem != 0) {
auto it = seen.find(rem);
if (it != seen.end()) {
res.insert(it->second, "(");
res += ')';
break;
}
seen[rem] = res.size();
rem *= 10;
res += (char)('0' + rem / den);
rem %= den;
}
return res;
}JavaScript
var fractionToDecimal = function(numerator, denominator) {
if (numerator === 0) return "0";
var sign = (numerator < 0) !== (denominator < 0) ? "-" : "";
var num = Math.abs(numerator), den = Math.abs(denominator);
var rem = num % den;
var whole = (num - rem) / den;
if (rem === 0) return sign + String(whole);
var digits = [];
var seen = new Map();
while (rem !== 0) {
if (seen.has(rem)) {
var at = seen.get(rem);
return sign + String(whole) + "." + digits.slice(0, at).join("") + "(" + digits.slice(at).join("") + ")";
}
seen.set(rem, digits.length);
rem *= 10;
var d = Math.floor(rem / den);
digits.push(String(d));
rem -= d * den;
}
return sign + String(whole) + "." + digits.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets