Fraction to Recurring Decimal — LeetCode 166 Python Solution
MediumHash TableMathString
- Problem
- #166
- Pattern
- Math and Number Theory
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- numerator = 1, denominator = 2
- Output
- "0.5"
Python solution
Python
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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(l) |
| Space | O(l), where l is the length of the result auxiliary |
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 166. Fraction to Recurring Decimal is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 166. Fraction to Recurring Decimal?
- LeetCode 166. Fraction to Recurring Decimal is rated Medium on LeetCode.
- What is the time complexity of LeetCode 166. Fraction to Recurring Decimal?
- The Python solution on this page runs in O(l).
- What is the space complexity of LeetCode 166. Fraction to Recurring Decimal?
- The Python solution on this page uses O(l), where l is the length of the result auxiliary space.
- What topics does LeetCode 166. Fraction to Recurring Decimal cover?
- LeetCode 166. Fraction to Recurring Decimal is tagged Hash Table, Math and String on LeetCode.