166. Fraction to Recurring Decimal
Model: qwen3.5:9b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 22.4%
Problem Breakdown
We are given two integers, numerator and denominator, representing a fraction. Our goal is to convert this into its decimal string representation. The critical requirement here is handling repeating decimals: if the fractional part repeats infinitely, we must enclose that sequence in parentheses (e.g., “0.(3)”).
Inputs: Two integers within standard 32-bit range (-2^31 to 2^31 - 1).
Outputs: A string representing the decimal.
Implicit Constraints & Edge Cases:
- Signs: Negative numbers need correct sign handling (e.g.,
-50 / 8 = "-6.25"). If both are negative, result is positive. - Integer Results: If
numeratordivides evenly bydenominator, there should be no decimal point or parentheses (e.g.,"4", not"4."). - Zero Numerator: Should return
"0". - Cycle Detection: We must detect when a remainder repeats to identify the start of an infinite loop. Since we are guaranteed that the answer length is manageable (< 10^4), we don’t need arbitrary precision libraries, but standard integer arithmetic in Python handles large numbers naturally anyway.
Intuition
Let’s simulate long division manually. We divide numerator by denominator. If there is a remainder, we multiply it by 10 and continue dividing to get the next decimal digit.
A brute-force approach might be to just keep generating digits until the string gets too long or time runs out, but that fails for infinite repeating decimals (like ). We need an algorithmic way to stop when a cycle is detected.
The key insight in division-based problems involving cycles lies in the remainder. In any base-10 division process, if we encounter a remainder that we have seen before before reaching 0, it means the sequence of digits generated between those two occurrences will repeat forever.
Therefore:
- We track remainders using a Hash Map (Dictionary).
- The key is
remainder, and the value is the index in our result string where that remainder first appeared. - If we see a remainder again, we know exactly where to insert parentheses around the substring between its first occurrence and now.
Approach
- Handle Signs: Work with absolute values for calculation logic to avoid Python’s floor division quirks (e.g.,
-5 // -2vs math expectation). Determine if the final result should be negative based on whether exactly one ofnumeratorordenominatoris negative. - Integer Part: Perform integer division (
abs(numerator) // abs(denominator)). Append this to our buffer string. Update remainder:remainder = numerator % denominator. - Check for Zero Remainder: If the remainder becomes zero, we are done; return the result immediately (no decimal point needed if no fractional part exists yet? Wait, check logic here. Actually, append
., then loop). Correction: Only add a decimal point and enter the loop ifremainder != 0. - Fractional Part Loop:
- Multiply remainder by 10 (shift left for next digit calculation).
- Calculate quotient:
(remainder * 10) // denominator-> append to buffer. - Update remainder:
(remainder * 10) % denominator. - Cycle Check: If this new
remainderexists in our map, we found a cycle. Insert parentheses around the substring frommap[remainder] + 1to current end of string. Break loop. - Otherwise, store
{new_remainder: len(buffer)}and continue.
Complexity Analysis
- Time: where is the length of the resulting decimal string (bounded by constraints). We perform constant time dictionary lookups/insertions per digit generated. Since we stop at either 0 remainder or a repeated remainder, we process each unique state once.
- Space: . We store the result string and the map mapping remainders to indices in that same order of magnitude as the output length.
Solution
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
# Handle sign logic separately using absolute values for math safety
if numerator == 0:
return "0"
negative = (numerator < 0) ^ (denominator < 0)
num, den = abs(numerator), abs(denominator)
result = []
# Integer part of the division
integer_part = num // den
remainder = num % den
if denominator == 1:
return "-" + str(integer_part) if negative else str(integer_part)
# Append decimal point and start fractional logic
result.append(str(integer_part))
if remainder != 0:
result.append('.')
seen_remainders = {}
index_map = len(result) - 1
while remainder != 0:
if remainder in seen_remainders:
# Cycle detected, insert parentheses around repeating part
start_index = seen_remainders[remainder] + 1
result.insert(start_index, '(')
result.append(')')
break
seen_remainders[remainder] = len(result) - 1
remainder *= 10
digit = remainder // den
remainder %= den
result.append(str(digit))
return "-" + "".join(result) if negative else "".join(result)
Edge Cases Handled
- Negative Inputs: Logic uses
abs()for calculation and a boolean flag to prepend-only when necessary. Handles cases like-1 / -2 = "0.5"correctly. - Zero Numerator: Explicitly returns
"0". - Exact Division (No Remainder): If remainder becomes 0, the loop terminates naturally without adding parentheses or a trailing decimal point if not needed (though logic adds
.only if initial remainder exists). Correction in code: The current implementation appends.immediately after integer part. This is correct for cases like “1/2” -> “0.”, then digit ‘5’. For exact division, the loop doesn’t run because we checkremainder != 0before appending., but wait… if remainder becomes 0 inside loop?- If initial remainder is non-zero (e.g., 1/3), we append ’.’, enter loop. Remainder eventually repeats or hits 0.
- If integer division leaves no remainder initially,
remainder != 0check prevents appending decimal point and entering the fractional logic block entirely? No, wait. - Let’s trace:
num=2,den=1.integer_part=2.remainder=0. Code checksif denominator == 1: returns “2”. - What about
4/3->"1.(3)". Integer part 1, remainder 1. Append., enter loop. Remainder repeats? No, it cycles eventually. - Wait, my code has a specific check for
denominator == 1. That’s an optimization but not strictly necessary if logic holds. - Crucial Logic Check: If I have
num=4, den=3, remainder is 1. Loop runs. Map stores{1: index}. Remainder becomes(1*10)%3 = 1. Next iteration sees1in map -> Insert parens. Correct. - Terminating Case:
num=1, den=2. Integer part 0, remainder 1. Append., enter loop.- Iteration 1: rem=1 not seen. Map
{1: index}. Rem becomes(1*10)%2 = 0. Digit ‘5’. - Loop condition
remainder != 0fails next check? No, inside loop we update remainder at end. - Next iteration start:
while remainder != 0: checks if rem is 0 (it was updated to 0). Loop terminates naturally without parens. Correct.
- Iteration 1: rem=1 not seen. Map
Note:* The code handles the case where a terminating decimal occurs by simply exiting the while loop when remainder becomes zero, avoiding parentheses insertion.**