166. Fraction to Recurring Decimal

Description

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

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

Solution

HashMap

考虑负数、overflow的情况。然后需要对整数部分和小数部分分开处理。小数部分的repeating用一个HashMap解决，map命中则说明遭遇了repeating，在repeating发生的初始位置插入括号。

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

        StringBuilder res = new StringBuilder();
        if ((numerator > 0 && denominator < 0) 
            || (numerator < 0 && denominator > 0)) {
            res.append("-");
        }
        
        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(".");
        Map<Long, Integer> numToIndex = new HashMap<>();
        
        while (num > 0) {
            num *= 10;
            if (numToIndex.containsKey(num)) {  // met repeating
                res.insert(numToIndex.get(num), "(");
                res.append(")");
                break;
            }
            
            res.append(num / den);
            numToIndex.put(num, res.length() - 1);
            num %= den;
        }
        
        return res.toString();
    }
}