Fraction to Recurring Decimal

LeetCode Q 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, input: numerator = 1, denominator = 2; output: “0.5”
input: numerator = 2, denominator = -1; output: “-2”
input: numerator = 2, denominator = 3; output: “0.(6)”

Solution

Key point is to consider all edge cases while thinking this problem through, including: negative integer, possible overflow, how to deal with repeated remainder.

Use HashMap to store a remainder and its associated index while doing the division so that whenever a same remainder comes up, we know there is a repeating fractional part.

Code:

public String fractionToDecimal(int numerator, int denominator) {
	if (numerator == 0) return "0";
	StringBuilder res = new StringBuilder();

	// deal with negative result
	if ((numerator > 0) ^ (denominator > 0)) sb.append("-");
	long num = Math.abs((long) numerator); // when charing Integer.MIN_VALUE to positive number
	long den = Math.abs((long) denominator); //if we still use int type, this will cause integer overflow.

	// integer part:
	res.append(num / den);
	num %= den;
	if (num == 0) return res.toString();

	// fractional part:
	res.append(".");
	Map<Long, Integer> map = new HashMap<Long, Integer>();
	map.put(num, res.length());
	while (num != 0) {
		num *= 10;
		res.append(num / den);
		num %= den;
		if (map.containsKey(num)) {
			res.insert(map.get(num), '(');
			res.append(')');
			break;
		} else {
			map.put(num, res.length());
		}
	}
	
	return res.toString();
}