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)".

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        StringBuilder sb = new StringBuilder();
        sb.append((numerator > 0) ^ (denominator > 0) ? "-" : "");

        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);

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

        sb.append(".");
        Map<Long, Integer> hash = new HashMap<>();
        hash.put(num, sb.length());

        while (num != 0){
            num *= 10;
            sb.append(num / den);
            num %= den;

            if (hash.containsKey(num)){
                int index = hash.get(num);
                sb.insert(index, "(");
                sb.append(")");
                break;
            }
            else{
                //System.out.println("num: " + num + " length: " + sb.length());
                hash.put(num, sb.length());
            }
        }

        return sb.toString();
    }
}