Fraction to Recurring Decimal | Leetcode

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

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

---

Solution: Watch out for negative numbers and boundary integer values in the input. First append the whole number part before the decimal point (straightforward). Loop to append the decimal numbers digit by digit. The way to do this is to use the formula: digit = (remainder * 10 / denominator). Keep track of the starting position of each remainder. If we get a remainder that we have seen before, enclose the recurring portion in parentheses and return. Else the remainder will go down to zero eventually so return when that happens.

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return "NaN";
        
        StringBuilder sb = new StringBuilder();
        
        // Fix negatives.
        long numer = numerator;
        long denom = denominator;
        if ((numerator < 0) ^ (denominator < 0)) {
            sb.append('-');
            if (numerator < 0) numer = -numer;
            if (denominator < 0) denom = -denom;
        }
        
        // Append number till decimal point.
        sb.append(numer / denom);
        long remainder = numer % denom;
        if (remainder == 0) return sb.toString();
        sb.append('.');
        
        // Append decimal numbers.
        Map<Long, Integer> indexOfRemainder = new HashMap<>();
        do {
            // Found recurring number, so insert parentheses and return.
            if (indexOfRemainder.containsKey(remainder)) {
                int index = indexOfRemainder.get(remainder);
                sb.insert(index, '(').append(')');
                break;
            }
            
            // Insert next digit.
            indexOfRemainder.put(remainder, sb.length());
            remainder *= 10;
            sb.append(remainder / denom);
            remainder %= denom;
        } while (remainder != 0);
        
        return sb.toString();
    }
}