LeetCode 166 - Fraction to Recurring Decimal

LeetCode Problem 166

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String

Solution

Problem Understanding

This problem asks us to convert a fraction, represented by an integer numerator and an integer denominator, into its decimal string representation. If the decimal expansion contains a repeating fractional sequence, we must enclose the repeating part in parentheses.

For example, the fraction 1/2 produces "0.5" because it terminates. The fraction 1/3 produces "0.(3)" because the digit 3 repeats forever. Similarly, 4/333 becomes "0.(012)" because the repeating cycle is "012".

The input consists of two integers:

• numerator, the top part of the fraction
• denominator, the bottom part of the fraction

The output is a string representation of the exact decimal value of the fraction.

The constraints tell us several important things:

• Both numerator and denominator may be negative.
• Values can be as large as 2^31 - 1 or as small as -2^31.
• denominator != 0, so division by zero is not a concern.
• The result length is guaranteed to be less than 10^4, meaning we do not need to worry about infinitely growing output.

The key challenge is identifying repeating decimals correctly. A naive implementation using floating point arithmetic will fail because floating point numbers cannot precisely represent repeating decimals and may introduce rounding errors.

Several edge cases can easily trip up an implementation:

• Negative numbers, where the result must include the correct sign.
• Fractions that divide evenly, such as 2/1, which should return "2" instead of "2.0".
• Repeating decimals, such as 1/3 or 2/7.
• Large values near integer limits, especially -2^31, where overflow may occur in some languages if absolute values are handled incorrectly.
• Zero numerators, where the result should simply be "0".

Approaches

Brute Force Approach

A brute-force solution would simulate long division digit by digit and keep appending decimal digits indefinitely until a pattern appears. One naive way to detect repetition would be to repeatedly compare suffixes of the generated decimal string to see whether some sequence is repeating.

This works because long division eventually either terminates or enters a cycle. A repeating decimal always repeats due to the finite number of possible remainders.

However, this approach is inefficient. Detecting repetition by scanning previously generated digits repeatedly can become expensive, especially if many digits are generated before repetition becomes obvious. Since each digit generation could require checking a large portion of the existing result, the time complexity becomes unnecessarily high.

Key Insight

The important observation is that repeating decimals arise because of repeated remainders during long division.

When dividing, each step depends entirely on the current remainder. If the same remainder appears again, the division process will repeat exactly from that point onward, producing the same digits forever.

For example, in 1/3:

• 1 ÷ 3 = 0 remainder 1
• Multiply remainder by 10: 10 ÷ 3 = 3 remainder 1

The remainder 1 repeats, so the digit sequence repeats.

This suggests using a hash map to record the position in the result string where each remainder first appeared. When we encounter the same remainder again, we know exactly where the repeating cycle starts and can insert parentheses.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates division and repeatedly checks for repeating patterns inefficiently
Optimal	O(n)	O(n)	Uses a hash map to track remainders and detect cycles efficiently

Here, n represents the number of digits produced in the decimal representation.

Algorithm Walkthrough

Optimal Algorithm

1. Handle the zero numerator case immediately

If numerator == 0, return "0" immediately. Regardless of the denominator, zero divided by anything nonzero is zero. 2. Determine the sign of the result

The result is negative if exactly one of numerator or denominator is negative. This is equivalent to checking whether their signs differ.

We append "-" to the result only if necessary. 3. Convert values to absolute numbers

Since the sign has already been handled, we convert both values to their absolute form. This simplifies division logic.

This step is especially important for avoiding issues with negative remainders. 4. Compute the integer portion

Use integer division:

integer_part = numerator // denominator

Append this to the result. 5. Compute the initial remainder

Use modulo:

remainder = numerator % denominator

If the remainder is 0, the decimal terminates, so return the result immediately. 6. Start processing the fractional part

Append "." to the result because there is a decimal component. 7. Use a hash map to track remainder positions

Create a dictionary:

remainder_position[remainder] = current_index

The key is the remainder, and the value is the index in the result where digits generated from this remainder begin. 8. Simulate long division

While the remainder is nonzero:

• If the remainder has appeared before:

• Retrieve its stored index.

• Insert "(" at that position.

• Append ")" at the end.

• Return the result.

• Otherwise:

• Store the current remainder position.

• Multiply remainder by 10.

• Compute the next digit:

digit = remainder // denominator

• Append the digit.
• Update:

remainder = remainder % denominator

9. Return the completed result

If the remainder eventually becomes 0, the decimal terminates naturally.

Why it works

The correctness relies on a fundamental property of long division: the next digit is completely determined by the current remainder. Since there are only finitely many possible remainders, either the remainder eventually becomes 0, producing a terminating decimal, or a previously seen remainder repeats. When a remainder repeats, the exact same sequence of operations repeats, guaranteeing a recurring cycle. By storing the first occurrence of each remainder, we can identify precisely where the repeating sequence begins and insert parentheses correctly.

Python Solution

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        result = []

        # Handle sign
        if (numerator < 0) ^ (denominator < 0):
            result.append("-")

        numerator = abs(numerator)
        denominator = abs(denominator)

        # Integer part
        integer_part = numerator // denominator
        result.append(str(integer_part))

        remainder = numerator % denominator

        # No fractional part
        if remainder == 0:
            return "".join(result)

        result.append(".")

        # Map remainder -> index in result
        remainder_position = {}

        while remainder != 0:
            if remainder in remainder_position:
                repeat_index = remainder_position[remainder]
                result.insert(repeat_index, "(")
                result.append(")")
                break

            remainder_position[remainder] = len(result)

            remainder *= 10
            digit = remainder // denominator
            result.append(str(digit))

            remainder %= denominator

        return "".join(result)

The implementation begins by handling the simplest case where the numerator is zero. This avoids unnecessary work and immediately returns "0".

The sign is handled before converting values to absolute numbers. The XOR operation checks whether exactly one value is negative, which indicates a negative result.

The integer portion is computed first because every decimal representation begins with it. If the remainder is zero after integer division, the decimal terminates and no further processing is needed.

For recurring decimals, the implementation enters a long division loop. The remainder_position dictionary is the core of the algorithm. Each remainder is mapped to the index where its resulting digit sequence begins. When a remainder repeats, the algorithm inserts "(" at the stored index and appends ")" at the end, correctly marking the recurring portion.

Using a list for result is more efficient than repeated string concatenation because strings are immutable in Python.

Go Solution

func fractionToDecimal(numerator int, denominator int) string {
	if numerator == 0 {
		return "0"
	}

	var result []byte

	// Handle sign
	if (numerator < 0) != (denominator < 0) {
		result = append(result, '-')
	}

	num := int64(numerator)
	den := int64(denominator)

	if num < 0 {
		num = -num
	}
	if den < 0 {
		den = -den
	}

	// Integer part
	integerPart := num / den
	result = append(result, []byte(strconv.FormatInt(integerPart, 10))...)

	remainder := num % den

	// No fractional part
	if remainder == 0 {
		return string(result)
	}

	result = append(result, '.')

	// Map remainder -> index
	remainderPosition := make(map[int64]int)

	for remainder != 0 {
		if pos, exists := remainderPosition[remainder]; exists {
			result = append(result[:pos],
				append([]byte{'('},
					append(result[pos:], ')')...)...)
			break
		}

		remainderPosition[remainder] = len(result)

		remainder *= 10
		digit := remainder / den
		result = append(result, byte('0'+digit))

		remainder %= den
	}

	return string(result)
}

The Go implementation follows the same algorithmic structure as Python, but there are a few language-specific considerations.

Most importantly, integer overflow must be handled carefully. Since numerator and denominator may equal -2^31, taking abs(-2^31) in a 32-bit integer can overflow. To avoid this, the implementation converts both values to int64 before taking absolute values.

Go does not support direct string insertion efficiently, so the solution manipulates a []byte slice. The remainder-to-position mapping works exactly the same way as in Python, but uses map[int64]int.

The code also uses strconv.FormatInt to convert integers into strings.

Worked Examples

Example 1: numerator = 1, denominator = 2

Initial setup:

result = []
numerator = 1
denominator = 2

Step	Action	Result	Remainder Map
1	Integer part = 0	["0"]	{}
2	Add decimal point	["0", "."]	{}
3	Store remainder 1	["0", "."]	{1: 2}
4	1 × 10 = 10, digit = 5	["0", ".", "5"]	{1: 2}
5	remainder = 0	"0.5"	{1: 2}

Final answer:

"0.5"

Example 2: numerator = 2, denominator = 1

Step	Action	Result
1	Integer part = 2	["2"]
2	remainder = 0	return "2"

Final answer:

"2"

Example 3: numerator = 4, denominator = 333

Iteration	Remainder	Digit Produced	Result	Map
Start	4	-	0.	{}
1	4	0	0.0	{4: 2}
2	40	1	0.01	{4: 2, 40: 3}
3	67	2	0.012	{4: 2, 40: 3, 67: 4}
4	4 repeats	-	0.(012)	detected cycle

Final answer:

"0.(012)"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each unique remainder is processed at most once
Space	O(n)	The hash map stores previously seen remainders

The algorithm is linear in the number of generated digits because each remainder can only appear once before either terminating or repeating. Since there are at most denominator unique remainders, the loop cannot run indefinitely.

Test Cases

solution = Solution()

assert solution.fractionToDecimal(1, 2) == "0.5"          # finite decimal
assert solution.fractionToDecimal(2, 1) == "2"            # integer result
assert solution.fractionToDecimal(4, 333) == "0.(012)"    # repeating cycle

assert solution.fractionToDecimal(1, 3) == "0.(3)"        # simple repeating digit
assert solution.fractionToDecimal(2, 3) == "0.(6)"        # repeating with different digit
assert solution.fractionToDecimal(1, 6) == "0.1(6)"       # mixed terminating + repeating

assert solution.fractionToDecimal(-1, 2) == "-0.5"        # negative numerator
assert solution.fractionToDecimal(1, -2) == "-0.5"        # negative denominator
assert solution.fractionToDecimal(-1, -2) == "0.5"        # double negative

assert solution.fractionToDecimal(0, 5) == "0"            # zero numerator
assert solution.fractionToDecimal(50, 8) == "6.25"        # terminating decimal

assert (
    solution.fractionToDecimal(-2147483648, 1)
    == "-2147483648"
)  # int boundary

assert (
    solution.fractionToDecimal(-2147483648, -1)
    == "2147483648"
)  # overflow-sensitive case

assert solution.fractionToDecimal(1, 7) == "0.(142857)"   # long repeating cycle
assert solution.fractionToDecimal(22, 7) == "3.(142857)"  # integer + repeating

Test	Why
1 / 2	Validates a simple terminating decimal
2 / 1	Ensures pure integer results return without decimal point
4 / 333	Confirms recurring cycle detection
1 / 3	Tests single-digit repetition
1 / 6	Verifies mixed finite and repeating fractional part
Negative inputs	Ensures sign handling is correct
0 / 5	Tests zero numerator shortcut
-2147483648 / -1	Validates overflow-sensitive edge case
1 / 7	Tests longer recurring sequence
22 / 7	Verifies integer and repeating portions together

Edge Cases

Zero Numerator

When numerator = 0, the answer must always be "0" regardless of the denominator. A naive implementation might proceed into division logic unnecessarily or accidentally return "0.0". This implementation handles the case immediately with an early return.

Negative Numbers

Handling signs incorrectly is a common source of bugs. For example, -1/2 and 1/-2 should both produce "-0.5", while -1/-2 should produce "0.5". The implementation separates sign handling from arithmetic by determining the sign first, then converting both values to absolute numbers.

Repeating Decimal Detection

Fractions like 1/3 or 1/7 never terminate. Without cycle detection, the algorithm could run forever. The implementation prevents this by storing previously seen remainders in a hash map. Once a remainder repeats, the recurring cycle is identified and enclosed in parentheses.

Integer Overflow Near Bounds

The input range includes -2^31, which can overflow if abs() is applied in languages with fixed-width integers. In Go, the implementation converts values to int64 before taking absolute values, ensuring safe arithmetic even for extreme inputs.