Online Judge Solutions

Tuesday, December 16, 2014

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)".
 
class Solution {
public:
    
    string fractionToDecimal(int numerator, int denominator) {
       
       bool isNeg = false;
       
       if ((numerator >0 && denominator < 0) || (numerator < 0 && denominator > 0))
          isNeg = true;
       string output = to_string(num / den);
       
       long long rem = num % den;
       if (rem != 0) {       
           output.push_back('.');
           unordered_map<int, int> map;
           
           map[rem] = output.length();
           while(rem > 0) {
               rem *= 10;
               output.push_back('0' + rem/den);
               rem = rem % den;
               if (map.count(rem) == 1) {
                  output.insert(map[rem], "(");
                  output.push_back(')');
                  break;
               }
               map[rem] = output.length();
           }
       }
       
       if (isNeg) output.insert(0, "-");
       
       return output;
    }
};

No comments:

Post a Comment