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.

Tips:

• 个人觉得这道题难死了，找循环的部分，用括号括起来。

• 拟除法运算。关键就是处理循环小数部分。。。用hash表记录余数的位置。如果余数重复出现的话，那就是出现了循环小数。

  Use HashMap to store a remainder and its associated index while doing the division so that whenever a same remainder comes up, we know there is a repeating fractional part.

• 但是，测试用例真心碉堡了。会出现（INT_MIN）/(-1)这样的测试case，因为INT_MIN的绝对值比INT_MAX要大1，所以即使输入的都是int，但是中间结果很可能越界。所以需要使用long long。

• The important thing is to consider all edge cases while thinking this problem through, including: negative integer, possible overflow, etc.

• 这样记录每一位小数，放入map，直到出现重复，则加括号。

  num *= 10;
  res.append(num / den);
  num %= den;
  

Code:

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder res = new StringBuilder();
        // "+" or "-"
        res.append((numerator < 0 == denominator < 0 || numerator == 0) ? "" : "-");
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);

        // integral part
        res.append(num / den);
        num %= den;
        if (num == 0) {
            return res.toString();
        }

        // fractional part
        res.append(".");
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        map.put(num, res.length());
        System.out.println(res.length());
        while (num != 0) {
            num *= 10;
            res.append(num / den);
            System.out.println(res.length());
            num %= den;
            if (map.containsKey(num)) {
                int index = map.get(num);
                res.insert(index, "(");
                res.append(")");
                break;
            }
            else {
                map.put(num, res.length());
            }
        }
        return res.toString();
    }
}