BiruLyu
8/4/2017 - 11:54 PM

## 166. Fraction to Recurring Decimal(#).java

``````public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder fraction = new StringBuilder();
// If either one is negative (not both)
if (numerator < 0 ^ denominator < 0) {
fraction.append("-");
}
// Convert to Long or else abs(-2147483648) overflows
long dividend = Math.abs(Long.valueOf(numerator));
long divisor = Math.abs(Long.valueOf(denominator));
fraction.append(String.valueOf(dividend / divisor));
long remainder = dividend % divisor;
if (remainder == 0) {
return fraction.toString();
}
fraction.append(".");
Map<Long, Integer> map = new HashMap<>();
while (remainder != 0) {
if (map.containsKey(remainder)) {
fraction.insert(map.get(remainder), "(");
fraction.append(")");
break;
}
map.put(remainder, fraction.length());
remainder *= 10;
fraction.append(String.valueOf(remainder / divisor));
remainder %= divisor;
}
return fraction.toString();
}``````
``````public class Solution {

// 9 / 7
// 9. 264513 26
// 1.(285714)28

// 68 / 131

// 1 / 6
public String fractionToDecimal(int numerator, int denominator) {
StringBuilder result = new StringBuilder();
if (numerator > 0 && denominator < 0 ||
numerator < 0 && denominator > 0) {
result.append("-");
}
long num = Math.abs((long)numerator);
long den = Math.abs((long)denominator);
result.append(num / den); // result: "0.16"
long mod = num % den; // 1 % 6 = 1
if (mod != 0) { // true
result.append("."); // result
Map<Integer, Integer> numerators = new HashMap<>();
int index = result.length(); // index = 2
do {
num = mod * 10; // 40
mod = num % den; // 40 % 6 = 4
if (numerators.containsKey((int)num)) { // false
int parenthesesStart = numerators.get((int)num);
result.insert(parenthesesStart, "(");
result.append(")");
break;
} else {
numerators.put((int)num, index); // {10->2;40->3}
}
result.append((long)(num / den)); // result
index++; // index = 4
} while (mod != 0);
}
return result.toString();
}
}``````
``````public class Solution {
private long gcd (long x, long y) {
return y == 0 ? x : gcd(y, x % y);
}
public String fractionToDecimal(int numerator, int denominator) {
StringBuilder sb = new StringBuilder();
if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
// sign = -1;
sb.append('-');
}
long n = Math.abs((long)numerator);
long d = Math.abs((long)denominator);
long g = gcd(n,d);
n /= g;
d /= g;
if (d == 1) {
sb.append(n);
return sb.toString();
}
else if (n == d) return "1";
HashMap<Long, Integer> map = new HashMap<>();
if (n > d) {
sb.append(n/d);
n = n % d;
if (n == 0) return sb.toString();
} else {
sb.append(0);
}
sb.append('.');
while (n != 0) {
if (map.containsKey(n)) {
//sb.insert(map.get(n), "(");
sb.insert((int)map.get(n), '(');
sb.append(')');
return sb.toString();
}
map.put(n, sb.length());
n *= 10;
long quotient = n / d;
sb.append(quotient);
n = n % d;
}
return sb.toString();
}
}``````