166. Fraction to Recurring Decimal (Medium)
https://leetcode.com/problems/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.
Example 1:
Input: numerator = 1, denominator = 2 Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1 Output: "2"
Example 3:
Input: numerator = 2, denominator = 3 Output: "0.(6)"
Solutions
class Solution {
// This problem is not easy to get over, you need to pay close attention to the special cases.
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0) {
return "";
}
if (numerator == 0) {
return "0";
}
int sign = 1;
if (numerator * 1.0 * denominator < 0) {
sign = -1;
}
// following statement is not correct.
// long num = Math.abs(numerator);
// long denom = Math.abs(denominator);
long num = Math.abs(numerator * 1l);
long denom = Math.abs(denominator * 1l);
// first get the integer
long itg = num / denom;
String ans = itg + "";
// if it is not exactly divisible. append dot
long remainder = num % denom;
if (remainder != 0) {
ans += ".";
}
// length of answer string
int count = ans.length();
// keep track of occurred remainders
Map<Long, Integer> map = new HashMap<>();
// 2 / 3, remainder is 2, remainder * 10 = 20
// second get the fraction
while (remainder != 0) {
remainder *= 10;
// fractional part is repeating
if (map.containsKey(remainder)) {
int idx = map.get(remainder);
ans = ans.substring(0, idx) + '(' + ans.substring(idx, count) + ')';
break;
}
map.put(remainder, count);
long frac = remainder / denom;
ans += frac;
remainder = remainder % denom;
count++;
}
if (sign < 0) {
ans = "-" + ans;
}
return ans;
}
}