Sponsored
Sponsored
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
1def fractionToDecimal(numerator, denominator):
2 if numerator == 0:
3 return "0"
4
5 result = []
6
7 if (numerator < 0) ^ (denominator < 0):
8 result.append("-")
9
10 numerator, denominator = abs(numerator), abs(denominator)
11
12 result.append(str(numerator // denominator))
13 remainder = numerator % denominator
14
15 if remainder == 0:
16 return ''.join(result)
17
18 result.append(".")
19 position_map = {}
20
21 while remainder:
22 if remainder in position_map:
23 result.insert(position_map[remainder], "(")
24 result.append(")")
25 break
26
27 position_map[remainder] = len(result)
28 remainder *= 10
29 result.append(str(remainder // denominator))
30 remainder %= denominator
31
32 return ''.join(result)The code starts by checking if the numerator is zero, in which case '0' is returned since no fraction can be formed. Then, it determines the sign of the result by checking if the numerator and denominator have opposite signs.
The result list is used to build the final string. Initially, we append the integral part of the division. If there's no remainder after this division, the process stops.
If there is a remainder, we enter a loop to handle the fractional part of the division. A map keeps track of the positions of previously seen remainders. If a remainder repeats, it indicates the start of a repeating sequence and parentheses are added around the sequence.