Fraction to Recurring Decimal

Medium
1271.

Fraction to Recurring Decimal

Fraction to Recurring Decimal is a medium coding problem on strings, hash table and math, asked in Amazon, Google, Meta and Rubrik interviews.

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 / 8 is -6.25; 4 / 2 is 2).
  • If it repeats, put the shortest repeating block, starting as early as possible, in parentheses (1 / 6 is 0.1(6), not 0.(16) or 0.16(6)).
  • A negative value starts with -; zero is written 0.

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 - 1
  • denominator != 0
  • The answer string is shorter than 10^4 characters for every test
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} numerator
 * @param {number} denominator
 * @return {string}
 */
var fractionToDecimal = function(numerator, denominator) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 / 8 is -6.25; 4 / 2 is 2).
  • If it repeats, put the shortest repeating block, starting as early as possible, in parentheses (1 / 6 is 0.1(6), not 0.(16) or 0.16(6)).
  • A negative value starts with -; zero is written 0.

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 - 1
  • denominator != 0
  • The answer string is shorter than 10^4 characters for every test

Hints for Fraction to Recurring Decimal

  1. 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.

  2. Hint 2

    The digits start repeating exactly when a remainder repeats — the next digits are determined by the remainder alone.

  3. 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

  1. If numerator == 0, return 0. Otherwise write - if exactly one of the inputs is negative.
  2. Switch to 64-bit absolute values n and d (because |-2^31| does not fit in 32 bits). Append n / d; let r = n % d. If r == 0, return.
  3. Append .. While r != 0: if r was seen before at output position p, insert ( at p, append ) and stop; otherwise remember r → current length, set r *= 10, append the digit r / d, and set r %= d.
  4. 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 / -1 and abs(-2147483648) overflow 32-bit integers — convert to 64-bit first.
  • 0 / -5 is 0, 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