[Leetcode]07/09 [Hash]Fraction to Recurring Decimal

/* Method1: Time:O(); Space:O(n), map Logic: Use remainder to judge recurring or not 1. sign 2. long 3. check remainder 0.16 _______ 6 ) 1.00 0 1 0 <-- data-blogger-escaped--="" data-blogger-escaped-16="" data-blogger-escaped-1="" data-blogger-escaped-36="" data-blogger-escaped-40="" data-blogger-escaped-4="" data-blogger-escaped-6="" data-blogger-escaped-as="" data-blogger-escaped-at="" data-blogger-escaped-before="" data-blogger-escaped-fractional="" data-blogger-escaped-is="" data-blogger-escaped-mark="" data-blogger-escaped-part="" data-blogger-escaped-position="1" data-blogger-escaped-remainder="4" data-blogger-escaped-repeating="" data-blogger-escaped-seen="" data-blogger-escaped-so="" data-blogger-escaped-starts="" data-blogger-escaped-the="" data-blogger-escaped-was="" data-blogger-escaped-which=""> 1(6). NOTE: map.put(rem, ans.length()-1); 1. 0.6 ans.length = 1 ans.length -1 = 0, put "(" at 0 0.(6) 2. 0.65 ans.length =2 ans.length -1 = 1, put "(" at 1 0.6(5) Method2: Time:O(); Space:O() Given numerator = 2, denominator = 3, return "0.(6)". Reference: 1.http://yuanhsh.iteye.com/blog/2176178 2.http://www.programcreek.com/2014/03/leetcode-fraction-to-recurring-decimal-java/ */

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        
        /*Method1: */
        // special case
        if ( denominator == 0 )
        {
            return "NaN";
        }
        if ( numerator == 0 )
        {
            return "0";
        }
        String sign = (denominator>>>31 ^ numerator>>>31) == 1 ? "-": "";
        Long num = (long)numerator, den = (long)denominator; // -2147483648 => 2147483648 okay, int.MAX_VALUE = 2147483647, Long.MAX_VALUE is 9,223,372,036,854,775,807.
        num = Math.abs(num);
        den = Math.abs(den);
        long major = num / den;
        long rem = num % den;
        // Case1: remainder == 0
        if ( rem == 0 )
        {
            return sign+major;
        }
        // Case2: remainder != 0
        String pre = sign + major + ".";
        StringBuilder ans = new StringBuilder();
        HashMap map = new HashMap();
        while (  rem != 0 )
        {
            // get the remainder+'0' / dennominator
            int res = (int) (rem*10 / den );  
            if (  map.containsKey(rem) ) 
            {
                int insert_index = map.get(rem);
                ans.insert(insert_index, "(");
                ans.append(")"); // append at last index
                break;
            }
            else 
            {
                // append res first
                ans.append(res);
                map.put( rem, ans.length( )-1 );
            }
            rem = (rem*10)%den;
        }
        // insert pre at the most front
        return ans.insert(0, pre). toString();
        
        
        
        /*Method2: 
        if ( denominator == 0 )
        {
            return "NaN";
        }
        if ( numerator == 0 )
        {
            return "0";
        }
        String sign = ( numerator>>>31 ^ denominator>>>31 ) ==1 ?"-" :"" ;
        long num = (long) numerator, den = (long) denominator;
        num = Math.abs( num );
        den = Math.abs( den );
        long major = num / den;
        long rem = num % den;
        long rem_temp = rem;
        // Case 1: rem == 0
        if (  rem == 0 )
        {
            return sign+major;
        }
        // Case 2: rem != 0
        String pre = sign + major + ".";
        Set set = new LinkedHashSet();
        while ( !set.contains(rem) && rem != 0 )
        {
            set.add(rem);
            rem = (rem*10) % den;
        }
        // recurring   
        String part2 = "";
        Boolean repeated = false;
        for ( long i:set )
        {
            if ( i  == rem )
            {
                part2+="(";
                repeated = true;
            }
            part2 += (rem_temp*10)/ den;
            rem_temp = (rem_temp*10) %den;
        }
        if ( repeated )
        {
            part2+=")";
        }
        return pre+part2;
        */
    }
}