[LeetCode] Fraction to Recurring Decimal

Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a ). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.

Now we have solved the trickiest part of this problem.

There are some remaining problems to solve to achieve a bug-free solution.

1. Pay attention to the sign of the result;
2. Handle cases that may cause overflow like numerator = -2147483648, denominator = -1appropriately by using long long;
3. Handle all the cases of (1) no fractional part; (2) fractional part does not recur; and (3) fractional part recurs respectively.

To handle problem 3, we divide the division process into the integral part and the fractional part. For the fractional part, if it does not recur, then the remainder will become 0 at some point and we could return. If it does recur, the method metioned in the first paragraph has already handled it.

Taking all these into considerations, we have the following code. Note that I implement anint2str function, which may be replaced by the system to_string if you like.

 1 class Solution {
 2 public:
 3     string fractionToDecimal(int numerator, int denominator) {
 4         if (!numerator) return "0"; 
 5         string res;
 6         if (numerator < 0 ^ denominator < 0) res += '-';
 7         long long numer = numerator < 0 ? (long long)numerator * (-1) : (long long)numerator;
 8         long long denom = denominator < 0 ? (long long)denominator * (-1) : (long long)denominator;
 9         long long integral = numer / denom;
10         res += int2str(integral);
11         long long rmd = numer - integral * denom;
12         if (!rmd) return res;
13         res += '.';
14         rmd *= 10;
15         map<long long, long long> mp;
16         while (rmd) {
17             long long quotient = rmd / denom;
18             if (mp.find(rmd) != mp.end()) {
19                 res.insert(mp[rmd], 1, '(');
20                 res += ')';
21                 break;
22             }
23             mp[rmd] = res.size();
24             res += int2str(quotient);
25             rmd = (rmd - denom * quotient) * 10;
26         }
27         return res;
28     }
29 private:
30     string int2str(long long num) {
31         string str;
32         while (num) {
33             int digit = num % 10;
34             str += digit + '0';
35             num /= 10;
36         }
37         if (str.empty()) return "0";
38         reverse(str.begin(), str.end());
39         return str; 
40     }
41 };