[LeetCode] Fraction to Recurring Decimal

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,

• 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: The integer part is trivial, and for the decimal part, we simulate the division procedure. A hash map is used to detect whether it is repeating. The tricky part is to deal with overflow/underflow. For example, see line 5 - 9, and line 24. The following Java code did not aim to take care of all the corner cases, and it only aimed to pass the LeetCode OJ, i.e., the test cases provided by the LeetCode OJ platform.
Alternatively, one may use type long to resolve possible overflow/underflow issues. See, e.g. this post.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

public class Solution { public String fractionToDecimal(int numerator, int denominator) { int n = numerator; int d = denominator; if (n == Integer.MIN_VALUE) { String s = n + ""; if (d == 1) return s; if (d == -1) return s.substring(1); } if (1.0 * n / d < 0) { return "-" + fractionToDecimal(-n, d); } int int_part = n / d; StringBuffer sb = new StringBuffer(); sb.append(int_part); n = n - d * int_part; if (n == 0) { return sb.toString(); } sb.append('.'); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int idx = sb.toString().length() - 1; while (n != 0) { int digit = (int) (1.0 * n / d * 10); sb.append(digit); idx++; map.put(n, idx); n = 10 * n - d * digit; if (map.containsKey(n)) { sb.append(')'); sb.insert((int)map.get(n), '('); return sb.toString(); } } return sb.toString(); } }