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

Analysis

• Consider cases:
  • numerator=0 (take care at first)
  • sign: negative or positive (take care at first)
  • overflow (cast numerator and denominator to long)
  • repeating fractional part: keep a hashmap to record value and position

Code

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if(numerator==0) {return "0";}
        StringBuilder sb = new StringBuilder();
        //very consice for sign! 
        sb.append((numerator>0)^(denominator>0)?"-":"");
        if(numerator/denominator<0) {sb.append("-");}
        long num=Math.abs((long)numerator);
        long den=Math.abs((long)denominator);

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

        //fractional part
        sb.append(".");
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        map.put(num, sb.length());
        while(num!=0){
            num*=10;
            sb.append(num/den);
            num%=den;

            if(map.containsKey(num)){
                sb.insert(map.get(num),"(");
                sb.append(")");
                return sb.toString();
            }
            else{
                map.put(num,sb.length());
            }
        }

        return sb.toString();

    }
}

Note

• Concise way for sign assigning: sb.append((numerator>0)^(denominator>0)?"-":"")
• sb.append(int, long, double...), append string version of number to stringbuilder

Reference

Leetcode