166. Fraction to Recurring Decimal (Medium)

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:

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

Solution:

这道题还是比较有意思的，开始还担心万一结果是无限不循环小数怎么办，百度之后才发现原来可以写成分数的都是有理数，而有理数要么是有限的，要么是无限循环小数，无限不循环的叫无理数，例如圆周率pi或自然数e等，小学数学没学好，汗！由于还存在正负情况，处理方式是按正数处理，符号最后在判断，那么我们需要把除数和被除数取绝对值，那么问题就来了：由于整型数INT的取值范围是-2147483648～2147483647，而对-2147483648取绝对值就会超出范围，所以我们需要先转为long long型再取绝对值。那么怎么样找循环呢，肯定是再得到一个数字后要看看之前有没有出现这个数。为了节省搜索时间，我们采用哈希表来存数每个小数位上的数字。还有一个小技巧，由于我们要算出小数每一位，采取的方法是每次把余数乘10，再除以除数，得到的商即为小数的下一位数字。等到新算出来的数字在之前出现过，则在循环开始出加左括号，结束处加右括号。代码如下：

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 = -1 appropriately 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 become0at 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, which takes 0 ms :-)

string fractionToDecimal(int numerator, int denominator) {
    if (!numerator) return "0";
    string res;
    if (numerator < 0 ^ denominator < 0) res += '-';
    long num = numerator < 0 ? (long)numerator*(-1) : (long)numerator;
    long den = denominator < 0 ? (long)denominator*(-1) : (long)denominator;
    long integral = num/den, rem = num%den;
    res += to_string(integral);
    if (rem == 0) return res;
    res += '.';
    unordered_map<long, long> mp;
    rem *= 10;
    while (rem) {
        if (mp.find(rem) != mp.end()) {
            res.insert(mp[rem],1,'(');
            res += ')';
            break;
        }
        mp[rem] = res.size();
        long quotient = rem/den;
        res += to_string(quotient);
        rem = (rem%den)*10;
    }

    return res;
}