LeetCode - Fraction to Recurring Decimal
Problem description
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:
1
2
Input: numerator = 1, denominator = 2
Output: "0.5"
Example 2:
1
2
Input: numerator = 2, denominator = 1
Output: "2"
Example 3:
1
2
Input: numerator = 2, denominator = 3
Output: "0.(6)"
Analysis
Just use a hashmap to store previous index and reminder.
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
38
39
40
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator % denominator == 0){
return String.valueOf((long)numerator / denominator);
}
StringBuilder sb = new StringBuilder();
HashMap<Long, Integer> map = new HashMap<>();
boolean flag = (numerator < 0 && denominator < 0) || (numerator >0 && denominator > 0);
String res = flag ? "" : "-" ;
numerator = -Math.abs(numerator);
denominator = -Math.abs(denominator);
res += String.valueOf(numerator / denominator) + ".";
long nu = numerator % denominator;
while (nu != 0){
if (map.containsKey(nu)){
break;
}
else{
map.put(nu, sb.length());
sb.append(nu * 10 / denominator);
nu = nu * 10 % denominator;
}
}
if (nu != 0){
sb.insert(map.get(nu), "(");
sb.append(')');
}
return res+sb.toString();
}
}
What to improve
- the edge cases, the negative number, the min and max of Integer, the overflow of Integer.