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.
1using System;
2using System.Text;
3using System.Collections.Generic;
4
5public class Solution {
6 public string FractionToDecimal(int numerator, int denominator) {
7 if (numerator == 0) return "0";
8 StringBuilder result = new StringBuilder();
9 if ((numerator < 0) ^ (denominator < 0)) result.Append('-');
10 long num = Math.Abs((long)numerator);
11 long den = Math.Abs((long)denominator);
12 result.Append(num / den);
13 long remainder = num % den;
14 if (remainder == 0) return result.ToString();
15 result.Append('.');
16 Dictionary<long, int> map = new Dictionary<long, int>();
17 while (remainder != 0) {
18 if (map.ContainsKey(remainder)) {
19 result.Insert(map[remainder], "(");
20 result.Append(')');
21 break;
22 }
23 map[remainder] = result.Length;
24 remainder *= 10;
25 result.Append(remainder / den);
26 remainder %= den;
27 }
28 return result.ToString();
29 }
30}This C# solution follows the long division technique with a remainder map to find repeating sequences. It uses a Dictionary to track each remainder's position in the string.
If a remainder repeats, parentheses are inserted using the Insert method, and the string is returned with the repeated sequence enclosed.
C# specifics like StringBuilder make the string manipulation efficient.