0ms C++ Solution with Detailed Explanations


  • 50

    Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a ). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.

    Now we have solved the trickiest part of this problem.

    There are some remaining problems to solve to achieve a bug-free solution.

    1. Pay attention to the sign of the result;
    2. Handle cases that may cause overflow like numerator = -2147483648, denominator = -1 appropriately by using long long;
    3. Handle all the cases of (1) no fractional part; (2) fractional part does not recur; and (3) fractional part recurs respectively.

    To handle problem 3, we divide the division process into the integral part and the fractional part. For the fractional part, if it does not recur, then the remainder will become 0 at some point and we could return. If it does recur, the method metioned in the first paragraph has already handled it.

    Taking all these into considerations, we have the following code, which takes 0 ms :-)

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            if (!numerator) return "0";
            string res;
            if (numerator < 0 ^ denominator < 0) res += '-';
            long numer = numerator < 0 ? (long)numerator * (-1) : (long)numerator;
            long denom = denominator < 0 ? (long)denominator * (-1) : (long)denominator;
            long integral = numer / denom;
            res += to_string(integral);
            long rmd = numer % denom;
            if (!rmd) return res;
            res += '.';
            rmd *= 10;
            unordered_map<long, long> mp; 
            while (rmd) {
                long quotient = rmd / denom;
                if (mp.find(rmd) != mp.end()) { 
                    res.insert(mp[rmd], 1, '(');
                    res += ')';
                    break;
                }
                mp[rmd] = res.size();
                res += to_string(quotient);
                rmd = (rmd % denom) * 10;
            }
            return res;
        }
    };

  • 1
    X

    Thanks for the brilliant explanation. One minor remark: in int2str() it is not necessary to do num -= digit, since the integral division num /= 10 will handle it anyway.


  • 0

    Hi, xlingcc. Thank you for your nice remind. I have updated my code.


  • 2
    S

    You should use unordered_map instead of map because it leads to a better time compexity . even the above problem takes 0 ms if you just use unordered_map instead of map;


  • 0

    Hi, sanghi. I have updated my code. Thank you for your remind.


  • 0
    M

    Awesome, 10/10 would upvote. Some suggestions:

    long long rmd = numer - integral * denom;
    

    Can be

    long long rmd = numer % denom;
    

    and

    rmd = (rmd - denom * quotient) * 10;
    

    can be

    rmd = (rmd % demom ) * 10;

  • 0

    Hi, mymaydayya. Thank you for your nice suggestions :-) I have updated my code now.


  • 0
    Y

    Great solution, 1 question: Why using long long but not long?

    Thanks


  • 0

    Hi, yiting007. Thanks for your remind. In fact, in my local machine, long also has only 32 bits and so I get used to using long long. However, in the OJ, long is already enough :-) I have updated my code now.


  • 0

    HI

    If you submit the code for the first time and got passed, then you're so awesome! Because I think it's so difficult to cover all those corner cases, especially 0/-1=0 not =-0.


  • 0

    Hi, @clubmaster. Haha, I tried many times too.


  • 0

    @jianchao.li.fighter, then that makes me feel much better, haha :P.


  • 0
    F

    Your algorithm almost the same with me, but I think my code is more easy to read, so I post here to share with you:

    what I do is after got repeat pattern, use distance of this pattern as the position where to put first "(" (in this case ")" will directly put at the end)

    string fractionToDecimal(int numerator, int denominator) {
        if(!numerator) return "0";
    
        long long a = numerator, b = denominator;
        int signa = (a>0 ? 1 : -1), signb = (b>0 ? 1 : -1);
        unordered_map<int, int> h;
        string ret = (signa*signb<0?"-":"") + to_string(a/b);
        string remder;
    
        a *= signa, b *= signb;
        int counter = 0;
        for( a %= b ; a && !h.count(a); a %= b) {
            h[a%b] = counter++;
            a *= 10;
            remder += to_string(a/b);
        }
    
        if( a || !remder.empty() ) {
            ret += ".";
            if(!a) ret += remder;
            else {
                ret += remder.substr(0, h[a]) + "(" +  remder.substr(h[a]) + ")";
            }
        }
        return ret;
    }

  • 0
    K

    better use long long, cause long on some machine also takes 4 bytes with range same as int (–2,147,483,648 to 2,147,483,647)


  • 0
    V

    great solution. there is no way I can ever think of this 'shit' myself :-) . Even better is that you provide good explanation which saves much of the time


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.