BiruLyu
8/4/2017 - 11:54 PM

166. Fraction to Recurring Decimal(#).java

public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        return "0";
    }
    StringBuilder fraction = new StringBuilder();
    // If either one is negative (not both)
    if (numerator < 0 ^ denominator < 0) {
        fraction.append("-");
    }
    // Convert to Long or else abs(-2147483648) overflows
    long dividend = Math.abs(Long.valueOf(numerator));
    long divisor = Math.abs(Long.valueOf(denominator));
    fraction.append(String.valueOf(dividend / divisor));
    long remainder = dividend % divisor;
    if (remainder == 0) {
        return fraction.toString();
    }
    fraction.append(".");
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            fraction.insert(map.get(remainder), "(");
            fraction.append(")");
            break;
        }
        map.put(remainder, fraction.length());
        remainder *= 10;
        fraction.append(String.valueOf(remainder / divisor));
        remainder %= divisor;
    }
    return fraction.toString();
}
public class Solution {
    
    // 9 / 7
    // 9. 264513 26
    // 1.(285714)28
    
    // 68 / 131
    
    // 1 / 6
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder result = new StringBuilder();
        if (numerator > 0 && denominator < 0 || 
            numerator < 0 && denominator > 0) {
            result.append("-");
        }
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        result.append(num / den); // result: "0.16"
        long mod = num % den; // 1 % 6 = 1
        if (mod != 0) { // true
            result.append("."); // result
            Map<Integer, Integer> numerators = new HashMap<>();
            int index = result.length(); // index = 2
            do {
                num = mod * 10; // 40
                mod = num % den; // 40 % 6 = 4
                if (numerators.containsKey((int)num)) { // false
                    int parenthesesStart = numerators.get((int)num);
                    result.insert(parenthesesStart, "(");
                    result.append(")");
                    break;
                } else {
                    numerators.put((int)num, index); // {10->2;40->3}
                }
                result.append((long)(num / den)); // result
                index++; // index = 4
            } while (mod != 0);
        }
        return result.toString();
    }
}
public class Solution {
    private long gcd (long x, long y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder sb = new StringBuilder();
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            // sign = -1;
            sb.append('-');
        }
        long n = Math.abs((long)numerator);
        long d = Math.abs((long)denominator);
        long g = gcd(n,d);
        n /= g;
        d /= g;
        if (d == 1) {
            sb.append(n);
            return sb.toString();
        }
        else if (n == d) return "1";
        HashMap<Long, Integer> map = new HashMap<>();
        if (n > d) {
            sb.append(n/d);
            n = n % d;
            if (n == 0) return sb.toString();
        } else {
            sb.append(0);
        }
        sb.append('.');
        while (n != 0) {
            if (map.containsKey(n)) {
                //sb.insert(map.get(n), "(");
                sb.insert((int)map.get(n), '(');
                sb.append(')');
                return sb.toString();
            }
            map.put(n, sb.length());
            n *= 10;
            long quotient = n / d;
            sb.append(quotient);
            n = n % d;
        }
        return sb.toString();
    }
}