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

Solution: HashMap
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        String result = "";
        // 处理正负号
        if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
            result += "-";
        }
        
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
        
        // 处理小数点前的位数
        result += num / den;
        if (num % den == 0) {
            return result;
        }
        
        // 如果num % den != 0说明有余数，加上小数点
        result += ".";
        
        num %= den;
        HashMap map = new HashMap();
        num *= 10;
        while (num % den != 0 && !map.containsKey(num)) {
            map.put(num, result.length());
            result += num / den;
            num %= den;
            num *= 10;
        }
        
        if (num % den == 0) {  // fractional part is not repeating
            result += num / den;
            return result;
        } else {
            String str = result.substring(0, map.get(num)) + "(" + result.substring(map.get(num)) + ")";
            return str;
        }
    }
}