Fraction to Recurring Decimal

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)”.

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

10/9/2015 update

So many corner cases we need to take care.

1. use long variables for denominator, nominator, remainder and quotient to avoid overflow.
2. Convert denominator and nominator to non-negative integer and record the sign symbol in flag.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string ans;
        string integer;
        string fraction;
        unordered_map<long, int> map;//remain, index
        //index points to the digits that the recurring begins
        long above = numerator;
        long below = denominator;
        long remain = 0;
        int flag = 1;
        if(above < 0){
            above *= -1;
            flag *= -1;
        }
        if(below < 0){
            below *= -1;
            flag *= -1;
        }
        integer = to_string(above / below);
        remain = above % below;
        map[remain] = 0;
        int index = 0;
        int quotient;
        while(remain != 0){
            index++;
            quotient = (remain * 10) / below;
            remain = (remain * 10) % below;
            fraction.push_back(quotient + '0');
            if(map.find(remain) == map.end()){
                //a new remain
                map[remain] = index;
            }
            else{
                int start = map[remain];
                fraction.insert(fraction.begin() + start, '(');
                fraction.push_back(')');
                break;
            }
        }
        ans = integer;
        if(!fraction.empty()){
            ans.push_back('.');
            ans.append(fraction);
        }
        if(flag == -1 && stof(ans) != 0){
            ans.insert(ans.begin(),'-');
        }
        return ans;
    }
};

1. We must convert int to long to avoid overflow.
2. use flag to resolve negative quotient.

//Could the numerator and denominator be negative?
//Could the numerator be 0?
//Could the numerator or denominator excced 2^32

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string re;
        long lnumerator = numerator;
        long ldenominator = denominator;
        int flag = 1;
        //extreme case
        if(numerator == 0){
            re.push_back('0');
            return re;
        }
        
        if(lnumerator < 0){
            flag *= -1;
            lnumerator *= -1;
        }
        if(ldenominator < 0){
            flag*= -1;
            ldenominator *= -1;
        }
        //ordinary case
        //is it enough?
        string fraction;
        unordered_map<long, int> remainders;
        long integer = 0;
        long mod = 0;
        integer = lnumerator / ldenominator;
        mod = lnumerator % ldenominator;
        
        re = to_string(integer);
        if(flag == -1){
            re.insert(0, "-");
        }
        //just a integer
        if(mod == 0) return re;
        remainders[mod] = 0;
        while(mod != 0){
            mod = mod * 10;
            int quotient = mod / ldenominator;
            mod = mod % ldenominator;
            fraction.push_back(quotient + '0'); // BUG HERE: mod means next quotient will repeat rather than the current quotient
            if(remainders.find(mod) != remainders.end()){
                //mod exists in remainders
                string part1 = fraction.substr(0, remainders[mod]);
                string part2 = fraction.substr(remainders[mod], -1);
                re.push_back('.');
                re.append(part1);
                re.push_back('(');
                re.append(part2);
                re.push_back(')');
                return re;
            }
            else{
                //mod does not exists in remainders
                remainders[mod] = fraction.size();
            }
        }
        //the number is dividable
        re.push_back('.');
        re.append(fraction);
        return re;
        
    }
};