Skip to main content
Talentd

Fraction to Recurring Decimal - Solution & Explanation

MediumHash TableMathString22 min readAsked at: Amazon, Microsoft, Goldman Sachs +7
Practice this problem

Problem Statement

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 - 1
  • denominator != 0

Approach Overview

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.

Approach 1: Long Division with Remainder Tracking

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.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Mathematics + Hash Table

First, we check if the numerator is 0. If it is, we return "0" directly.

Next, we check if the numerator and denominator have different signs. If they do, the result is negative, and we set the first character of the result to "-".

Then we take the absolute values of the numerator and denominator, denoted as a and b. Since the range of the numerator and denominator is [-2^{31}, 2^{31} - 1], taking the absolute value directly may cause overflow, so we convert both a and b to long integers.

Next, we calculate the integer part, which is the integer part of a divided by b, convert it to a string, and add it to the result. Then we take the remainder of a divided by b, denoted as a.

If a is 0, it means the result is an integer, and we return the result directly.

Next, we calculate the decimal part. We use a hash table d to record the length of the result corresponding to each remainder. We continuously multiply a by 10, then add the integer part of a divided by b to the result, then take the remainder of a divided by b, denoted as a. If a is 0, it means the result is a finite decimal, and we return the result directly. If a has appeared in the hash table, it means the result is a recurring decimal. We find the starting position of the cycle, insert the result into parentheses, and then return the result.

The time complexity is O(l), and the space complexity is O(l), where l is the length of the result. In this problem, l < 10^4.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Long Division with Remainder Tracking

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.

Mathematics + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic Long Division SimulationO(n^2)O(1)Educational understanding of decimal expansion without extra memory
Long Division with Remainder Hash MapO(n)O(n)General case; efficiently detects repeating decimals during division

Video Solution

Fraction to Recurring Decimal (Leetcode 166) Solution | Hashmap Interview Question Playlist • Pepcoding • 24,731 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Fraction to Recurring Decimal easy or hard?
Fraction to Recurring Decimal is generally considered a medium difficulty problem. The arithmetic itself is simple, but correctly detecting repeating cycles, handling negative numbers, and avoiding overflow requires careful implementation.
Fraction to Recurring Decimal Python/Java solution
Most implementations follow the same logic: determine the sign, compute the integer part, and simulate long division for the fractional part. A hash map tracks remainders and their positions. The code structure is nearly identical across Python, Java, C++, C#, and JavaScript.
How to solve Fraction to Recurring Decimal in O(n)?
Perform long division and keep a hash map that records the index where each remainder first appeared in the result string. Multiply the remainder by 10 each step, append the digit from division, and update the remainder. If a remainder repeats, insert parentheses around the repeating substring.
What is the best approach for Fraction to Recurring Decimal?
The standard solution simulates long division while storing each remainder in a hash map. When a remainder repeats, the digits between the two occurrences form the repeating cycle. This approach runs in O(n) time and O(n) space, where n is the number of digits produced in the decimal expansion.
Is Fraction to Recurring Decimal asked at Google/Amazon/Meta?
Fraction to Recurring Decimal is a classic string and math interview problem that appears in technical interviews at large tech companies. Variants of the problem are reported in interviews at companies like Google, Amazon, and Meta because it tests simulation, hash maps, and edge case handling.
What data structure is used in Fraction to Recurring Decimal?
A hash table (hash map) is used to map each remainder to the index where its corresponding digit was added in the result string. This allows constant-time detection of repeating remainders, which indicates the start of a recurring decimal cycle.
What is the time complexity of Fraction to Recurring Decimal?
The optimal algorithm runs in O(n) time because each unique remainder appears at most once during long division. Since the number of possible remainders is bounded by the denominator, the loop terminates after at most n steps. Space complexity is also O(n) due to the hash map storing remainders and their positions.

Ready to solve this problem?

Practice Fraction to Recurring Decimal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters