How do you solve Fraction to Recurring Decimal on LeetCode?

Fraction to Recurring Decimal (LeetCode #166) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to perform long division is crucial for this problem.

What is the brute force solution for Fraction to Recurring Decimal?

The brute force approach for Fraction to Recurring Decimal is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves performing long division manually to find the decimal representation of the fraction. We will keep track of the remainder and the quotient to build the decimal string step by step. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Fraction to Recurring Decimal?

Fraction to Recurring Decimal uses the following concepts: Hash Table, Math, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Fraction to Recurring Decimal?

Explain your thought process clearly while coding. Test edge cases, such as negative numbers and zero. Be prepared to discuss the time and space complexity of your solution.

What are common mistakes when solving Fraction to Recurring Decimal?

Failing to handle negative signs correctly. Not using a hashmap to track remainders, leading to inefficient solutions.

#166

Fraction to Recurring Decimal

Medium

Hash TableMathStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution utilizes a hashmap to keep track of previously seen remainders, allowing us to efficiently identify repeating cycles in the decimal representation. This reduces unnecessary calculations and improves performance.

⚙️

Algorithm

3 steps

1Step 1: Calculate the integer part and handle the sign.
2Step 2: Use a hashmap to store the index of each remainder encountered during the division process.
3Step 3: When a remainder repeats, we can determine the start of the repeating section and format the result accordingly.

solution.py26 lines

1# Full working Python code
2
3def fractionToDecimal(numerator: int, denominator: int) -> str:
4    if numerator == 0:
5        return '0'
6    result = ''
7    if (numerator < 0) ^ (denominator < 0):
8        result += '-'
9    numerator, denominator = abs(numerator), abs(denominator)
10    integer_part = numerator // denominator
11    result += str(integer_part)
12    remainder = numerator % denominator
13    if remainder == 0:
14        return result
15    result += '.'
16    remainder_map = {}
17    decimal_part = ''
18    while remainder != 0:
19        if remainder in remainder_map:
20            decimal_part = decimal_part[:remainder_map[remainder]] + '({})'.format(decimal_part[remainder_map[remainder]:])
21            break
22        remainder_map[remainder] = len(decimal_part)
23        remainder *= 10
24        decimal_part += str(remainder // denominator)
25        remainder %= denominator
26    return result + decimal_part

ℹ

Complexity note: The complexity is O(n) because we process each digit of the decimal representation only once, and we store remainders in a hashmap for quick access.

1Understanding how to perform long division is crucial for this problem.
2Recognizing when a remainder repeats helps identify the start of a recurring decimal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.