Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
If multiple answers are possible, return any of them.
It is guaranteed that the length of the answer string is less than 104 for all the given inputs.
Example 1:
Input: numerator = 1, denominator = 2 Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1 Output: "2"
Example 3:
Input: numerator = 4, denominator = 333 Output: "0.(012)"
Constraints:
-231 <= numerator, denominator <= 231 - 1denominator != 0Problem 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.
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
The code starts by checking if the numerator is zero, in which case '0' is returned since no fraction can be formed. Then, it determines the sign of the result by checking if the numerator and denominator have opposite signs.
The result list is used to build the final string. Initially, we append the integral part of the division. If there's no remainder after this division, the process stops.
If there is a remainder, we enter a loop to handle the fractional part of the division. A map keeps track of the positions of previously seen remainders. If a remainder repeats, it indicates the start of a repeating sequence and parentheses are added around the sequence.
Java
C
C++
C#
JavaScript
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Long Division Simulation | O(n^2) | O(1) | Educational understanding of decimal expansion without extra memory |
| Long Division with Remainder Hash Map | O(n) | O(n) | General case; efficiently detects repeating decimals during division |
How to Convert Fractions to Recurring Decimals (Proportions Part 3/6) • Cognito • 148,586 views views
Watch 9 more video solutions →Practice Fraction to Recurring Decimal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor