Difficulty: Easy | Acceptance: 64.80% | Paid: No Topics: Array, Math
Given two integers numerator and denominator, return the decimal representation of the fraction numerator / denominator.
If the decimal part is repeating, enclose the repeating part in parentheses.
If multiple answers are possible, return any of them.
It is guaranteed that the length of the answer will be less than 10⁴ for all given inputs.
- Examples
- Constraints
- Long Division with Hash Map
- Long Division with Cycle Detection (Floyd’s Algorithm)
Examples
Example 1
Input:
n = 537
Output:
[500,30,7]
Explanation: We can express 537 as 500 + 30 + 7. It is impossible to express 537 as a sum using fewer than 3 base-10 components.
Example 2
Input:
n = 102
Output:
[100,2]
Explanation: We can express 102 as 100 + 2. 102 is not a base-10 component, which means 2 base-10 components are needed.
Example 3
Input:
n = 6
Output:
[6]
Explanation: 6 is a base-10 component.
Constraints
- 1 <= n <= 10^9
Long Division with Hash Map
Intuition We simulate the process of long division. The key observation is that a decimal representation repeats if and only if a remainder repeats during the division process. We use a hash map to store the first index where each remainder appears.
Steps
- Handle the sign of the result by checking if the numerator and denominator have different signs.
- Compute the integer part using absolute values.
- Initialize a map to store remainders and their corresponding positions in the result string.
- Perform the long division loop:
- If the remainder becomes 0, the division terminates.
- If the remainder is seen before, insert a ’(’ at the previously recorded index and append ’)’ to the result.
- Otherwise, record the current remainder’s position, multiply it by 10, and append the resulting digit to the result.
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
res = []
# Determine sign
if (numerator < 0) ^ (denominator < 0):
res.append("-")
# Work with absolute values
n, d = abs(numerator), abs(denominator)
# Integer part
res.append(str(n // d))
remainder = n % d
if remainder == 0:
return "".join(res)
res.append(".")
# Map remainder to index in res
remainder_map = {}
while remainder != 0:
if remainder in remainder_map:
# Repeating part found
res.insert(remainder_map[remainder], "(")
res.append(")")
break
remainder_map[remainder] = len(res)
remainder *= 10
res.append(str(remainder // d))
remainder %= d
return "".join(res)
Complexity
- Time: O(D), where D is the number of digits in the result. In the worst case, we iterate until the remainder repeats or becomes 0.
- Space: O(D), to store the result string and the hash map of remainders.
- Notes: This approach is straightforward and handles all edge cases, including negative numbers and integer overflow.
Long Division with Cycle Detection (Floyd’s Algorithm)
Intuition We can optimize space complexity by using Floyd’s Cycle-Finding Algorithm (Tortoise and Hare) to detect the repeating cycle in the sequence of remainders without storing all of them. Once a cycle is detected, we can regenerate the string.
Steps
- Calculate the integer part and initial remainder.
- Use two pointers (slow and fast) to traverse the sequence of remainders. The slow pointer moves one step at a time, while the fast pointer moves two steps.
- If they meet, a cycle exists. Find the start of the cycle (mu) by resetting one pointer to the beginning and moving both one step at a time.
- Regenerate the decimal string up to the start of the cycle, then add the repeating part in parentheses.
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
res = []
if (numerator < 0) ^ (denominator < 0):
res.append("-")
n, d = abs(numerator), abs(denominator)
res.append(str(n // d))
remainder = n % d
if remainder == 0:
return "".join(res)
res.append(".")
# Helper to get next remainder
def get_next(r):
return (r * 10) % d
# Floyd's Cycle Detection
slow = remainder
fast = get_next(remainder)
while slow != fast and fast != 0:
slow = get_next(slow)
fast = get_next(get_next(fast))
# If fast is 0, no cycle (terminating decimal)
if fast == 0:
curr = remainder
while curr != 0:
curr *= 10
res.append(str(curr // d))
curr %= d
return "".join(res)
# Find start of cycle (mu)
mu = 0
ptr1 = remainder
ptr2 = slow
while ptr1 != ptr2:
ptr1 = get_next(ptr1)
ptr2 = get_next(ptr2)
mu += 1
# Generate non-repeating part
curr = remainder
for _ in range(mu):
curr *= 10
res.append(str(curr // d))
curr %= d
res.append("(")
# Generate repeating part
# We know it repeats, so we loop until we see the start remainder again
start_rem = curr
while True:
curr *= 10
res.append(str(curr // d))
curr %= d
if curr == start_rem:
break
res.append(")")
return "".join(res)
Complexity
- Time: O(D), where D is the number of digits. We traverse the sequence to find the cycle and then again to build the string.
- Space: O(D) for the result string, but O(1) auxiliary space (excluding the output) since we do not store the remainders in a map.
- Notes: This approach is more complex to implement but optimizes auxiliary space usage.