Accepted C++ Solution


  • 0
    A

    Idea is similar. You have to remember the remainder you have seen before and at what position. At any given point of time if you see a known remainder, you have reached the end of the part that's repeated.

    C++ Code

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            std::stringstream ss;
            long pos = 0;
            long rem = numerator;
            long d = denominator;
            if(rem == 0)
            {
                return "0";
            }
            
            string pref = "";
            if(rem < 0 && d > 0)
            {
                rem = rem * (-1);
                pref = "-";
            }
            else if(rem < 0 && d < 0)
            {
                rem = rem * (-1);
                d *= (-1);
            }
            else if(rem > 0 && d < 0)
            {
                pref = "-";
                d *= (-1);
                
            }
    
            if(rem >= d)
            {
                long mul = rem/d;
                ss << mul;
                rem = rem%d;
                long len = (mul == 0 ? 1 : (long)(log10(mul)+1));
                pos = pos + len;
            }
            
            std::map<long, long> seen;
            if(rem == 0)
            {
                return pref + ss.str();
            }
            else
            {
                if(pos == 0)
                {
                    ss << '0';
                    pos++;
                }
                ss << '.';
                pos++;
                seen.insert(pair<long, long>(rem, pos-1));
            }
            bool fs = true;
            
            while(true)
            {
                rem = rem*10;
                
                if(rem == 0)
                {
                    return pref + ss.str();
                }
    
                while(rem < d)
                {
                    ss << "0";
                    pos++;
                    long old = rem;
                    rem *= 10;
                    seen.insert(pair<long,long>(old, pos - 1));
                }
                
                long mul;
                if(rem == d)
                {
                    mul = rem/d;
                    ss << mul;
                    return pref + ss.str();
                }
                else
                {
                    mul = rem/d;
                    ss << mul;
                    rem = rem%d;
                    pos++;
                    
                    if(seen.find(rem) == seen.end())
                    {
                        seen.insert(pair<long,long>(rem, pos - 1));
                    }
                    else
                    {
                        long repStart = seen.find(rem)->second;
                        long end = pos;
                        
                        string tot = ss.str();
                        
                        // Cut till repStart
                        string first = tot.substr(0, repStart + 1);
                        long len = end - repStart;
                        string rep  = tot.substr(repStart + 1, len);
                        
                        // return the concatenation.
                        return pref + first + "(" + rep + ")";
                    }
                }
            }
        }
    };
    
    

Log in to reply
 

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