166 Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses. For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".

Hint:

• No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
• Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
• Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

Solution

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        // a/b
        if ( denominator == 0 ) return "";
        if ( numerator == 0 ) return "0";
        bool isNeg = true;
        if ( long(numerator) > 0 and long(denominator) > 0 ) {
            cout << "1" << endl;
            isNeg = false;
        }
        if ( long(numerator) < 0 and long(denominator) < 0 ) {
            cout << "2" << endl;
            isNeg = false;
        }
        long a = abs(long(numerator)), b = abs(long(denominator));
        string res= "";
        // find the the integer part:
        res += to_string(a/b);
        if ( a%b == 0 ) {
            if ( isNeg ) res = "-" + res;
            return res;
        }
        res += ".";
        a = (a%b)*10;
        unordered_map<int, int> map;
        while ( true ) {
            if ( map.find(a) != map.end() ) {
                int i = map[a];
                res = res.substr(0, i) + '(' + res.substr(i) + ')';
                break;
            }
            long tmp1 = a/b, tmp2 = a%b;
            res += to_string(tmp1);
            map[a] = int(res.size()) - 1;
            if ( tmp2 == 0 ) break;
            a = tmp2*10;
        }
        if ( isNeg )  res = "-"+res;
        return res;
    }
};

Notes
非常非常注意overflow的case和负数。好累。。。