164. Fraction to Recurring Decimal
You are handed two integers, numerator and denominator, that together describe the fraction numerator / denominator. Return that fraction written out as a decimal string.
Some fractions never terminate — their digits eventually fall into a cycle. When that happens, wrap exactly the repeating block in parentheses: 2 / 3 becomes "0.(6)", and 7 / 12 becomes "0.58(3)" because only the 3 repeats.
Follow the usual conventions: no unnecessary trailing zeros (1 / 2 is "0.5", not "0.50"), a whole-number result carries no decimal point (4 / 2 is "2"), a zero numerator is just "0", and a single leading - appears when the true value is negative (-1 / 2 → "-0.5").
The classic trap: the repeating cycle is detected through the remainders of long division, not the digits themselves.
Example 1:
Input: numerator = 1, denominator = 2
Output: "0.5"
Explanation: 1 divided by 2 terminates after one digit, so no parentheses are needed.
Example 2:
Input: numerator = 2, denominator = 3
Output: "0.(6)"
Explanation: 2 / 3 = 0.6666… — the digit 6 repeats forever, so it is wrapped in parentheses.
Example 3:
Input: numerator = 4, denominator = 333
Output: "0.(012)"
Explanation: 4 / 333 = 0.012012012… — the three-digit block 012 cycles.
Constraints:
- -2³¹ ≤ numerator, denominator ≤ 2³¹ - 1
- denominator ≠ 0
- The answer string is guaranteed to have fewer than 10⁴ characters.
Hints:
Do the division the way you learned in school: pull off the integer part, then repeatedly multiply the remainder by 10 to produce the next fractional digit.
Each fractional digit is determined entirely by the current remainder. If a remainder ever shows up a second time, the digits between its first appearance and now form the repeating block.
Remember where each remainder first occurred — a hash map from remainder to digit position lets you slice the cycle out in O(1). Watch the sign: work with absolute values (in a 64-bit type, since |INT_MIN| overflows 32 bits) and prepend '-' when exactly one input is negative.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: numerator = 1, denominator = 2
Expected output: "0.5"