Skip to content

Fraction to Recurring Decimal

Tim_Gao edited this page Sep 14, 2016 · 1 revision
  1. deal with negative number
  2. deal with Integer overflow
  3. deal with 0
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder res = new StringBuilder(); 
        boolean isNegative = false;
        long ln = (long) numerator, ld = (long) denominator;
        if(numerator < 0){
            isNegative = !isNegative;
            ln = -ln;
        }
        if (denominator < 0){
            isNegative = !isNegative;
            ld = -ld;
        }
        if (isNegative && ln != 0){
            res.append("-");
        }
        res.append(ln/ld).append(".");
        ln = ln%ld;
        HashMap<Long, Integer> hm = new HashMap<>();
        while(ln!=0){
            ln *= 10; 
            long val = ln/ld;
            if (hm.containsKey(ln)){
                int start = hm.get(ln);
                String substr = res.substring(start);
                res.setLength(start);
                res.append("(").append(substr).append(")");
                break;
            }
            res.append(val);
            hm.put(ln, res.length()-1);
            ln = ln - val*ld;
        }   
        if (res.charAt(res.length()-1) == '.'){
            res.deleteCharAt(res.length()-1);
        }   
        return res.toString();
    }   
}

Clone this wiki locally