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.

Description Hints 4 Solution Video 35:03

166. Fraction to Recurring Decimal

Medium31.3% acceptance10 companies

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 10⁴ 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:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Asked at 10 companies

Ixl Goldman Sachs Zoho

Google Snapchat Meta Oracle Amazon Microsoft Bloomberg

Topics

Hints open one at a time

Hint 1

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?

Hint 2

Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?

Hint 3

Notice that once the remainder starts repeating, so does the divided result.

Hint 4

Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

35:03

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

1
2

Input

2
1

Input

4
333

Your code is saved on this device.Solution