Fraction to Recurring Decimal - Video Solutions

Problem Overview: You receive two integers representing a fraction: numerator / denominator. The task is to return the decimal representation as a string. If the fractional part repeats, enclose the repeating sequence in parentheses. For example, 1/3 becomes "0.(3)" and 2/4 becomes "0.5".

Approach 1: Basic Long Division Simulation (O(n^2) time, O(1) space)

The most direct idea is to simulate manual long division. Divide the numerator by the denominator to get the integer part, then repeatedly multiply the remainder by 10 and divide again to produce decimal digits. The challenge is detecting when digits start repeating. Without storing previously seen remainders, you must repeatedly scan the built string to detect cycles, which can degrade performance. This approach demonstrates the mechanics of long division but becomes inefficient as the repeating sequence grows.

Approach 2: Long Division with Remainder Tracking (O(n) time, O(n) space)

The optimal solution simulates long division but tracks each remainder in a hash table. Each remainder maps to the index in the output string where its digit first appeared. When the same remainder appears again, the digits between those indices form a repeating cycle. Insert an opening parenthesis at the first occurrence and append a closing parenthesis at the end. Handle sign separately and work with absolute values to avoid overflow. The algorithm repeatedly multiplies the remainder by 10, appends remainder / denominator to the result, and updates the remainder with remainder % denominator. Since each unique remainder is processed once, the runtime is O(n) where n is bounded by the denominator.

This method relies on properties of division from math and uses a string builder to construct the result efficiently. The key insight: repeating decimals occur when the same remainder reappears during long division.

Recommended for interviews: Interviewers expect the long division with remainder tracking solution. The brute simulation shows you understand how decimal expansion works, but the hash map optimization demonstrates algorithmic thinking and knowledge of cycle detection. The optimal approach runs in O(n) time with O(n) extra space and cleanly handles both terminating and repeating decimals.