[LeetCode] 166. Fraction to Recurring Decimal

Posted on | In

Problem

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

Explanation

  1. For example 1 / 6:

    1
    2
    3
    4
    5
    6
    7
    8
         0.16
 6 ) 1.00
     0
     1 0       <-- Remainder=1, mark 1 as seen at position=0.
     - 6
       40      <-- Remainder=4, mark 4 as seen at position=1.
     - 36
        4      <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).

  2. The key insight here is to notice that once the remainder starts repeating, so does the divided result.

  3. We will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.

  4. The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.

  5. Just like the question 29. Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as -2147483648 / -1.

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
30
31
32
33
34
35
36
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return "";
        StringBuilder res = new StringBuilder();

        if ((numerator < 0) ^ (denominator < 0)) res.append("-");

        long num = numerator, den = denominator;
        num = Math.abs(num);
        den = Math.abs(den);

        long ans = num / den;
        res.append(String.valueOf(ans));

        long rem = (num % den) * 10;
        if (rem == 0) return res.toString();

        Map<Long, Integer> hm = new HashMap<>();
        res.append(".");
        while (rem != 0) {
            if (hm.containsKey(rem)) {
                int begin = hm.get(rem);
                String part1 = res.toString().substring(0, begin);
                String part2 = res.toString().substring(begin, res.length());
                return part1 + "(" + part2 + ")";
            }
            hm.put(rem, res.length());
            ans = rem / den;
            res.append(String.valueOf(ans));
            rem = (rem % den) * 10;
        }

        return res.toString();
    }
}

Source:

【LeetCode】Fraction to Recurring Decimal【Solution】