166. 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:

Core: Use a hashmap to track the reminder and position in the stringbuilder. So stop calculating reminder when either of those two conditions is met:

a. The hashmap contains the reminder as the key, which means the result starts repeating

b. The reminder is 0, which means the result is a terminating decimal

If condition b is met, just return the string. If condition a is met, insert '(' to the repeating position by looking up the dictionary map we build and append ')' to the last then return the string.

Notes: 

Cast int to long to avoid integer overflow. 

Need to determine negative sign beforehand. eg -1 / 3, can't get negative sign if just append the quotient 

   public String fractionToDecimal(int numerator, int denominator) {  
    boolean negative=(numerator<0 && denominator>0) || (numerator>0 && denominator<0);  
    long n=Math.abs((long)numerator);  
    long d=Math.abs((long)denominator);  
    StringBuilder sb=new StringBuilder();  
    if(negative) sb.append('-');  
    sb.append(n/d);  
    if(n%d==0) return sb.toString();  
    sb.append('.');  
    n=Math.abs(n%d);  
    HashMap<Long,Integer> map=new HashMap<Long,Integer>();  
    while(!map.containsKey(n)){  
      map.put(n,sb.length());  
      sb.append(n*10/d);  
      n=n*10%d;  
      if(n==0) return sb.toString();  
    }  
     int pos=map.get(n);  
     sb.insert(pos,'(');  
     sb.append(')');  
     return sb.toString();     
   }