Fraction to Recurring Decimal

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atGoldman Sachs

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

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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (list of remainders, linear search)O(L²)O(L)
Optimal (hash map from remainder to position)O(L)O(L)

2Optimal (hash map from remainder to position)

TimeO(L)Each fraction digit costs O(1) expected time; L is bounded by the denominator and by the answer length limit.
SpaceO(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.

  1. Write the sign and integer part using 64-bit absolute values; return if the remainder is 0.
  2. Append '.'; while rem != 0: if rem is in the map, insert '(' at map[rem], append ')', stop.
  3. 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();
    }
}

Edge cases to test

  • 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

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.