166. Fraction to Recurring Decimal

• Difficulty: Medium

• Topics: Hash Table, Math

• Similar Questions:

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:

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

Solutions:

class Solution {
public:
    string fractionToDecimal(int n, int d) {

        int sign = 1;
        if (((n >> 31) & 1) != ((d >> 31) & 1))  sign = -1;

        long numerator = n;
        long denominator = d;

        numerator = abs(numerator);
        denominator = abs(denominator);

        long integral = numerator / denominator; // integral should be of type long
        numerator = numerator % denominator;

        string fractional;
        computeFraction(numerator * 10, denominator, fractional);

        string ret;
        if (numerator == 0 && integral == 0)    return "0"; // this is essential
        if (sign == -1) {
            ret.push_back('-');
        }

        ret.append(to_string(integral));
        if (numerator == 0) return ret;

        ret.push_back('.');
        ret.append(fractional);

        return ret;
    }

    void computeFraction(long numerator, long denominator, string& fractional) {
        vector<int> digits;
        unordered_map<int, int> indices;
        while (numerator != 0) {
            if (indices.count(numerator)) {
                int unRepeatingIndex = indices[numerator];
                for (int i = 0; i < unRepeatingIndex; ++i) {
                    fractional.push_back('0' + digits[i]);
                }
                fractional.push_back('(');
                for (int i = unRepeatingIndex; i < digits.size(); ++i) {
                    fractional.push_back('0' + digits[i]);
                }
                fractional.push_back(')');
                return;
            }
            int q = numerator / denominator;
            digits.push_back(q);
            indices[numerator] = digits.size() - 1;
            numerator = (numerator % denominator) * 10;
        }

        for (int i = 0; i < digits.size(); ++i) {
            fractional.push_back('0' + digits[i]);
        }

    }
};