Google
166 Fraction to Recurring Decimal

1. Question

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

2. Implementation

(1) Hash Table
1
class Solution {
2
public String fractionToDecimal(int numerator, int denominator) {
3
if (numerator == 0 || denominator == 1) {
4
return String.valueOf(numerator);
5
}
6
7
StringBuilder res = new StringBuilder();
8
if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
9
res.append("-");
10
}
11
12
long dividend = Math.abs((long)numerator);
13
long divisor = Math.abs((long)denominator);
14
15
//Integer Part
16
res.append(dividend / divisor);
17
dividend %= divisor;
18
19
if (dividend == 0) {
20
return res.toString();
21
}
22
23
// Fration Part
24
res.append(".");
25
Map<Long, Integer> map = new HashMap<>();
26
27
while (dividend != 0) {
28
if (map.containsKey(dividend)) {
29
int index = map.get(dividend);
30
res.insert(index, "(");
31
res.append(")");
32
break;
33
}
34
map.put(dividend, res.length());
35
dividend *= 10;
36
res.append(dividend / divisor);
37
dividend %= divisor;
38
}
39
return res.toString();
40
}
41
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), n为结果的长度, 空间复杂度O(n)