#166

Medium

LeetCode Problem Workspace

Fraction to Recurring Decimal

Convert a fraction into a decimal, handling repeating decimals with parentheses around the repeating part.

Problem Statement

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fraction has a repeating decimal, enclose the repeating part in parentheses. For example, 4/333 becomes '0.(012)'. If the fraction does not repeat, just return its exact decimal form.

If there are multiple possible correct outputs, any valid result is acceptable. The numerator and denominator will always be within the range of -231 to 231 - 1, and the denominator will not be zero. This problem is solvable with elementary math knowledge like long division and a hash table to track previously seen remainders.

Examples

Example 1

Input: numerator = 1, denominator = 2

Output: "0.5"

Example details omitted.

Example 2

Input: numerator = 2, denominator = 1

Output: "2"

Example details omitted.

Example 3

Input: numerator = 4, denominator = 333

Output: "0.(012)"

Example details omitted.

Constraints

-231 <= numerator, denominator <= 231 - 1
denominator != 0

Solution Approach

Use Long Division

Perform long division to convert the fraction into a decimal, detecting repeating cycles by tracking remainders. When a remainder repeats, you’ve found the start of the repeating decimal.

Hash Table for Remainders

Use a hash table to store each remainder along with its index in the decimal part. This allows you to easily identify when a remainder repeats and where the repeating cycle begins.

Handle Negative Numbers

Ensure proper handling of negative signs. The result should have a negative sign only if either the numerator or denominator is negative, but not both.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of digits in the decimal expansion before repeating, and space complexity depends on the number of remainders encountered. In the worst case, the time and space complexity are both O(N), where N is the number of digits before the decimal starts repeating.

What Interviewers Usually Probe

Check for the candidate's understanding of long division.
Evaluate their ability to track repeating decimals efficiently with hash tables.
Assess if the candidate is careful with edge cases like negative numbers and zero denominators.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly identify the repeating decimal pattern.
Not handling negative numbers properly, leading to incorrect results.
Not using a hash table efficiently, causing unnecessary recalculations of remainders.

Follow-up variants

Handle larger numbers in the numerator and denominator.
Allow more than one repeating decimal cycle (e.g., 1/7 = '0.(142857)').
Modify the problem to handle fractions where the result is an integer, avoiding decimals altogether.

FAQ

How do I handle repeating decimals in the 'Fraction to Recurring Decimal' problem?

You can use long division and a hash table to track remainders. When a remainder repeats, that means the decimal starts repeating from that point.

What is the time complexity of the 'Fraction to Recurring Decimal' problem?

The time complexity depends on the number of digits before the decimal repeats, which can be O(N), where N is the length of the repeating part.

Can the numerator and denominator be negative in this problem?

Yes, the fraction can be negative. The sign of the result should be negative if one of the numerator or denominator is negative, but not both.

What are the edge cases to consider for the 'Fraction to Recurring Decimal' problem?

Edge cases include handling negative numbers, zero denominators (which are invalid), and fractions that result in exact integers or repeating decimals.

What is the primary pattern to solve the 'Fraction to Recurring Decimal' problem?

The primary pattern is to use long division with a hash table to track remainders and identify repeating decimal cycles.

terminal

Solution

Solution 1: Mathematics + Hash Table

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        ans = []
        neg = (numerator > 0) ^ (denominator > 0)
        if neg:
            ans.append("-")
        a, b = abs(numerator), abs(denominator)
        ans.append(str(a // b))
        a %= b
        if a == 0:
            return "".join(ans)
        ans.append(".")
        d = {}
        while a:
            d[a] = len(ans)
            a *= 10
            ans.append(str(a // b))
            a %= b
            if a in d:
                ans.insert(d[a], "(")
                ans.append(")")
                break
        return "".join(ans)

Continue Practicing

#13 roman to integer #12 integer to roman #770 basic calculator iv