LeetCode

Fraction to Recurring Decimal

2015.1.23 15:59

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.

For example,

　　Given numerator = 1, denominator = 2, return "0.5".

　　Given numerator = 2, denominator = 1, return "2".

　　Given numerator = 2, denominator = 3, return "0.(6)".

Solution:

　　First of all, the denominator won't be 0. Next you should take care of the sign first, + or -, make it positive.

　　3 % 5 == 3

　　5 % 3 == 2

　　6 % 3 == 0

　　The process of calculating a rational fraction is actually by division and modulus. If the remainder is zero, you get a finite fraction, otherwise an infinite loop. There's gonna be a loop as long as it is rational fraction. So, you'll have to record the remainder sequence, with a hash table maybe. When the same remainder is encountered, you know you've found the loop sequence.

　　Also there's something to be careful about printing. Like the following.

　　5 / 3 == 1.(6)

　　0 / 3 == 0

　　6 / 3 == 2

　　1 / 7 == 0.(142857)

　　The denominator can be really large, so don't try to use an int A[MAXN] to record the sequence, it won't do. That's why I suggest hashing.

　　The time complexity is generally O(denominator), but should be much smaller in fact. The fraction 1 / n may have a loop sequence of at most n - 1 in length, but usually far shorter. Space complexity is the same scale.

Accepted code:

// 1RE, 1TLE, 3MLE, 1AC, watch out for boundary cases and memory limit
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

typedef long long int ll;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        ll n = numerator;
        ll d = denominator;

        int sn, sd;

        sn = n >= 0 ? 1 : -1;
        n = n >= 0 ? n : -n;
        sd = d >= 0 ? 1 : -1;
        d = d >= 0 ? d : -d;

        if (n == 0) {
            return "0";
        }

        string res = "";
        if (sn * sd < 0) {
            res.push_back('-');
        }

        ll q = n / d;
        ll r = n % d;

        res += to_string(q);

        if (r == 0) {
            return res;
        }

        res.push_back('.');
        int pos = (int)res.length();

        unordered_map<ll, int> seq;
        unordered_map<ll, int>::iterator it;

        while (r != 0) {
            it = seq.find(r);
            if (it != seq.end()) {
                res.insert(it->second, "(");
                res.push_back(')');
                return res;
            }
            seq[r] = pos;
            q = r * 10 / d;
            r = r * 10 % d;
            res.push_back((int)q + '0');
            ++pos;
        }

        seq.clear();
        return res;
    }
private:
};
/*
int main()
{
    int n, d;
    Solution sol;

    while (cin >> n >> d) {
        cout << sol.fractionToDecimal(n, d) << endl;
    }

    return 0;
}
*/