A Readable C++ Solution And Explanation


  • 1
    B

    Just like we doing Division, we try to take the current numerator to be divided by the denominator step by step. If the current numerator is less than the denominator, we append a '0' to make the former 10 times bigger. Or else, we do the division and get a single digit and a remainder which becomes the next numerator. If there is no positive remainder after a division, the process stops.

    Use a buffer to Record the numerators we get at every step, if we find the current numerator be the same as some one in the buffer, that means a repeating pattern has been created.

    Apart from the main idea, we also need to deal with some special cases, for example, the negative integers. int32 is not sufficient in this problem.

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            string ans;
            long long num = numerator, den = denominator;
            if((long long)num * den < 0)ans += '-';
            num = num > 0 ? num : -num;
            den = den > 0 ? den : -den;
            
            //get integer part
            char str[200];
            sprintf(str,"%lld",num/den);
            ans += str;
            
            //get fractional part
            num = num%den;
            if(num == 0)return ans;
            
            string fraction;
            
            vector<long long> buf;
            buf.push_back(num);
            
            while(true){
                bool isRepeating = false;
                for(int i = 0; i < buf.size() - 1; i ++){
                    if(buf[i] == num){
                        //is repeating
                        string repeating = "(";
                        repeating += fraction.substr(i,buf.size()-i);
                        repeating += ')';
                        fraction = fraction.substr(0,i) + repeating;
                        isRepeating = true;
                        break;
                    }
                }
                if(isRepeating)break;
                num *= 10;
                long long digit = num/den;
                fraction += '0' + digit;
                num = num - den*digit;
                if(num == 0)break;
                buf.push_back(num);
            }
            
            ans += '.';
            ans += fraction;
            return ans;
        }
    };

Log in to reply
 

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