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

Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division? Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern? Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

Solution

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0) return "0";

        long numer = (long) numerator;
        long denom = (long) denominator;

        boolean negative = numer * denom < 0;
        numer = numer < 0 ? -numer : numer;
        denom = denom < 0 ? -denom : denom;

        StringBuilder sb = new StringBuilder();
        sb.append( numer / denom ) ;
        numer %= denom;
        if(numer != 0) sb.append(".");
        List<Long> remain = new ArrayList<Long>();
        List<Long> ans = new ArrayList<Long>();
        boolean cycle = false;
        int cycleIdx = -1;
        while(numer != 0) {
            if(remain.contains(numer)) {
                cycle = true;
                cycleIdx = remain.indexOf(numer);
                break;
            }
            remain.add(numer);
            numer *= 10;
            ans.add(numer/denom);
            numer %= denom;
        }

        if(cycle) {
            for(int i = 0; i < ans.size(); i++) {
                if(i == cycleIdx) sb.append("(");
                sb.append(ans.get(i));
            }
            sb.append(")");
        } else {
            for(long a: ans) sb.append(a);
        }

        return negative? "-"+sb.toString() : sb.toString();
    }
}