Algorithm to Compute the Fraction to Recurring Decimal of the Two Integer Division

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:
Input: numerator = 1, denominator = 2
Output: “0.5”

Example 2:
Input: numerator = 2, denominator = 1
Output: “2”

Example 3:
Input: numerator = 2, denominator = 3
Output: “0.(6)”

Hints:
No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Notice that once the remainder starts repeating, so does the divided result.
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

A few test cases help us better design a solution.

1/0 – this should be INF
-1/0 – this should be -INF
24/3 – result is a integer 8 (without .0)
1/2 – result is half 0.5
0/0.5 – result is zero
-2/1 – result is negative -2
1/-2 – result is negative half -0.5
-1/-1 – result is positive 1 (with two negative division)
−2147483648/1 – result is −2147483648 (make sure integer don’t overflow when you do the absolute value)
etc..

The algorithm is just simple math. We compute the remainder, multiple by ten and repeat the same process until the remainder is zero or the remainder appears before – that will be the recurring fraction part/pattern. For example, 1/3=0.33333.

The intelligent part is to put the position of the remainder into the hash map and when the same remainder appears next, we know where to repeat from i.e. the start position.

The return type is string, thus when the denominator is zero, we can totoally return INF or -INF depending on the numerator. Alternatively, we can raise an exception – which seems a good approach as well.

C++:

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

class Solution {
public:
    string fractionToDecimal(int64_t numerator, int64_t denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return numerator >= 0 ? "INF" : "-INF";
        string r = std::to_string(abs(numerator) / abs(denominator));
        if (numerator < 0 ^ denominator < 0) {
            r = "-" + r;
        }
        numerator = abs(numerator);
        denominator = abs(denominator);
        int64_t rem = numerator % denominator;
        if (rem == 0) {
            return r;
        }
        r += ".";        
        unordered_map<int, int> data;
        while (rem != 0) {
            if (data.find(rem) != data.end()) {
                int x = data[rem];
                return r.substr(0, x) + "(" + r.substr(x) + ")";
            }
            data[rem] = r.size();
            rem *= 10;
            r += std::to_string(rem / denominator);
            rem %= denominator;
        }
        return r;
    }
};

class Solution {
public:
    string fractionToDecimal(int64_t numerator, int64_t denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return numerator >= 0 ? "INF" : "-INF";
        string r = std::to_string(abs(numerator) / abs(denominator));
        if (numerator < 0 ^ denominator < 0) {
            r = "-" + r;
        }
        numerator = abs(numerator);
        denominator = abs(denominator);
        int64_t rem = numerator % denominator;
        if (rem == 0) {
            return r;
        }
        r += ".";        
        unordered_map<int, int> data;
        while (rem != 0) {
            if (data.find(rem) != data.end()) {
                int x = data[rem];
                return r.substr(0, x) + "(" + r.substr(x) + ")";
            }
            data[rem] = r.size();
            rem *= 10;
            r += std::to_string(rem / denominator);
            rem %= denominator;
        }
        return r;
    }
};

Java: we use a StringBuilder to build the string.

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

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return (numerator >= 0) ? "INF" : "-INF"; 
        }
        if (numerator == 0) return "0";
        long a = Math.abs(Long.valueOf(numerator));
        long b = Math.abs(Long.valueOf(denominator));
        long rem = a % b;
        StringBuilder sb = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            sb.append('-');
        }
        sb.append(a / b);
        if (rem == 0) {
            return sb.toString();
        }
        sb.append('.');
        Map<Long, Integer> map = new HashMap<>();
        while (rem != 0) {
            if (map.containsKey(rem)) {
                sb.insert(map.get(rem), "(");
                sb.append(")");
                break;
            }
            map.put(rem, sb.length());
            rem *= 10;
            sb.append(rem / b);
            rem = rem % b;
        }
        return sb.toString();
    }
}

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return (numerator >= 0) ? "INF" : "-INF"; 
        }
        if (numerator == 0) return "0";
        long a = Math.abs(Long.valueOf(numerator));
        long b = Math.abs(Long.valueOf(denominator));
        long rem = a % b;
        StringBuilder sb = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            sb.append('-');
        }
        sb.append(a / b);
        if (rem == 0) {
            return sb.toString();
        }
        sb.append('.');
        Map<Long, Integer> map = new HashMap<>();
        while (rem != 0) {
            if (map.containsKey(rem)) {
                sb.insert(map.get(rem), "(");
                sb.append(")");
                break;
            }
            map.put(rem, sb.length());
            rem *= 10;
            sb.append(rem / b);
            rem = rem % b;
        }
        return sb.toString();
    }
}

The complexity (both time and space) is O(b) if we want to compute the a/b. That is because it has at most b different remainders and the algorithm will terminate after b iterations at least.

–EOF (The Ultimate Computing & Technology Blog) —