166. Fraction to Recurring Decimal

The trick to solve this problem is to get the recurring numbers. Since we don't know when recurring happens, for example, 4/333 = 0.(012) and 1/6 = 0.1(6), we have to record all the remainders that we have seen before. We can use hash map here to retrieve the previous remainders fast. Also, once we find the recurring remainder, we need to insert a left parenthesis before it so the key-value pair of the hash map is remainder-position.
Besides these, we need to take care of overflow which can be solved by long long and the negative number which we need a prefix "-".

1:  class Solution {  
2:  public:  
3:    string fractionToDecimal(int numerator, int denominator) {  
4:      if (!numerator) return "0";  
5:      int sign = (numerator < 0) ^ (denominator < 0) ? -1 : 1;  
6:      string res = (sign == -1) ? "-" : "";  
7:      long long n = labs(numerator);  
8:      long long d = labs(denominator);  
9:      res += to_string(n / d);  
10:      long long r = n % d;  
11:      if (r == 0) return res;  
12:      res += ".";  
13:      r *= 10;  
14:      unordered_map<long long, int> rm;  
15:      while (r) {  
16:        if (rm.find(r) != rm.end()) {  
17:          res.insert(rm[r], 1, '(');  
18:          res += ")";  
19:          break;  
20:        }  
21:        rm[r] = res.size();  
22:        res += to_string(r / d);  
23:        r = (r % d) *10;  
24:      }  
25:      return res;  
26:    }  
27:  };