LeetCode link

Intuition

  • Use a map to save the fractional index of each meet numerator.
  • When the map contains a numerator, so it’s a repeating fractional, the range is from the value of key to the current.
  • When the numerator can be divided at some point, so it’s not a repeating fractional, just return the string.

solution

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
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "NaN";
        }
        int integer = numerator / denominator;
        String result = integer + "";
        int remainder = numerator % denominator;
        if (remainder == 0) {
            return result;
        }
        result += ".";
        Map<Integer, Integer> map = new HashMap<>();
        String frac = "";
        int i = 0;
        remainder *= 10;
        while (remainder % denominator != 0 && !map.containsKey(remainder)) {
            frac += Integer.toString(remainder / denominator);
            map.put(remainder, i);
            remainder = (remainder % denominator) * 10;
            i++;
        }
        if (remainder % denominator == 0) {
            return result + frac + Integer.toString(remainder / denominator);
        }
        String repeat = frac.substring(map.get(remainder), i);
        return result + frac.substring(0, map.get(remainder)) + "(" + repeat + ")";
    }
}

problem

WA.

reason

Miss the negative numbers.

modification

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
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "NaN";
        }
        boolean isNeg = false;
        if (numerator * denominator < 0) {
            isNeg = true;
        }
        numerator = Math.abs(numerator);
        denominator = Math.abs(denominator);
        int integer = numerator / denominator;
        String result = integer + "";
        int remainder = numerator % denominator;
        if (remainder == 0) {
            return isNeg ? "-" + result : result;
        }
        result += ".";
        Map<Integer, Integer> map = new HashMap<>();
        String frac = "";
        int i = 0;
        remainder *= 10;
        while (remainder % denominator != 0 && !map.containsKey(remainder)) {
            frac += Integer.toString(remainder / denominator);
            map.put(remainder, i);
            remainder = (remainder % denominator) * 10;
            i++;
        }
        if (remainder % denominator == 0) {
            result = result + frac + Integer.toString(remainder / denominator);
            return isNeg ? "-" + result : result;
        }
        String repeat = frac.substring(map.get(remainder), i);
        result = result + frac.substring(0, map.get(remainder)) + "(" + repeat + ")";
        return isNeg ? "-" + result : result;
    }
}

problem

WA.

Input:
-1
-2147483648
Output:
“-0.0000000000000000000000000000001”
Expected:
“0.0000000004656612873077392578125”

reason

Precision.

modification

Use Long instead of int

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
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "NaN";
        }
        boolean isNeg = false;
        long n = (long)numerator;
        long d = (long)denominator;
        if (n * d < 0) {
            isNeg = true;
        }
        n = Math.abs(n);
        d = Math.abs(d);
        long l = n / d;
        String result = l + "";
        long remainder = n % d;
        if (remainder == 0) {
            return isNeg ? "-" + result : result;
        }
        result += ".";
        Map<Long, Integer> map = new HashMap<>();
        String frac = "";
        int i = 0;
        remainder *= 10;
        while (remainder % d != 0 && !map.containsKey(remainder)) {
            frac += Long.toString(remainder / d);
            map.put(remainder, i);
            remainder = (remainder % d) * 10;
            i++;
        }
        if (remainder % d == 0) {
            result = result + frac + Long.toString(remainder / d);
            return isNeg ? "-" + result : result;
        }
        String repeat = frac.substring(map.get(remainder), i);
        result = result + frac.substring(0, map.get(remainder)) + "(" + repeat + ")";
        return isNeg ? "-" + result : result;
    }
}