Fraction to Recurring Decimal
Medium · Math · Hash Table · Math · String
Problem
Given two integers numerator and denominator, return the value of numerator / denominator written as a decimal string.
If the digits after the decimal point repeat forever, put the repeating block in parentheses: 1/6 is "0.1(6)" and -22/7 is "-3.(142857)". Use the shortest form: the block starts as early as possible and is as short as possible ("0.(3)", not "0.3(3)" or "0.(33)"). A value with no fractional part has no decimal point ("2", not "2.0").
The answer is shorter than 10^4 characters.
Examples
Input: numerator = 5, denominator = 4 Output: "1.25"
5 / 4 = 1.25: the division ends after two digits.
Input: numerator = 1, denominator = 6 Output: "0.1(6)"
1 / 6 = 0.1666...: the 1 is written once, then the 6 repeats.
Input: numerator = -22, denominator = 7 Output: "-3.(142857)"
22 / 7 = 3.142857142857..., and exactly one input is negative.
Constraints
- -2^31 <= numerator, denominator <= 2^31 - 1
- denominator != 0
Approaches
- Baseline: search the list of earlier remainders — time O(L²), space O(L)
Follow-up
There are fewer than d possible non-zero remainders, so the fractional part terminates or starts repeating within d digits; that is why the answer is bounded. It terminates exactly when the reduced denominator has no prime factors other than 2 and 5. The use cases below ask only for the length of the repeating block, and for a single far-away digit without writing the ones before it.
Related problems
Start free on Cariara · Coding problems · System design studio
