Fraction to Recurring Decimal - Video Solutions

Problem Overview: You are given two integers numerator and denominator. Convert the fraction into its decimal representation as a string. If the decimal repeats, wrap the repeating portion in parentheses. Example: 1/3 becomes "0.(3)" and 2/4 becomes "0.5".

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

The straightforward idea is to simulate manual long division. First compute the integer part using numerator / denominator. Then repeatedly multiply the remainder by 10 and divide again to generate decimal digits. Store produced digits in a string while tracking seen remainders in a collection. If a remainder repeats, the decimal pattern starts repeating from the first occurrence. Without storing the exact position of the remainder, detecting the precise repeating segment becomes difficult, which limits this basic version.

This approach relies purely on arithmetic operations and iterative digit generation. It works because repeating decimals occur when the same remainder appears again during division. Time complexity is O(n) where n is the length of the generated decimal sequence. Space complexity is O(n) to store digits and previously seen remainders.

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

The optimal solution improves the previous idea by storing the index where each remainder first appeared. Use a hash table mapping remainder → position in result string. After computing the integer part, repeatedly multiply the remainder by 10 and append the digit (remainder * 10) / denominator. Update the remainder using modulus.

If the remainder becomes zero, the decimal terminates and the result is complete. If the remainder already exists in the hash map, a repeating cycle begins. Insert ( at the stored index and append ) at the end. This precisely captures the repeating block.

Edge cases matter. Handle negative numbers by determining the sign first. Convert values to 64‑bit integers to avoid overflow when using abs(). The algorithm combines arithmetic reasoning from math with efficient lookup from a hash table, while building the result using string operations. Time complexity remains O(n), where n is the number of produced digits before repetition. Space complexity is O(n) for the remainder map and output string.

Recommended for interviews: Interviewers expect the remainder tracking approach. Brute long division demonstrates understanding of how decimal expansion works, but using a hash table to detect the repeating remainder shows algorithmic thinking and familiarity with cycle detection patterns. Most accepted solutions in interviews and production implementations follow this method.