leetcode Question: Fraction to Recurring Decimal

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

Analysis:

This problem needs a little bit of thinking, but it's not difficult to handle. The key idea is not about programming, but the procedure of division.

For example, lets do 4/7, a table can be easily computed as follows:

dividend   divisor   quotient  remainder
     4               7            0               4
-----------------------------------------------
    40              7            5               5
    50              7            7               1
    10              7            1               3
    30              7            4               2
    20              7            2               6
    60              7            8               4
    40              7            5               5  

From the table we can see that, the quotient are the result:   0. (571428).
Why the computation stops?  Because the remainder occurred in previous steps.
How to get the new dividend?  10 times the remainder in previous round.

I think it is now pretty clear how to do the programming part.

Note that
(1) We need to handle the negative number(s).
(2) The remainders is better to save in a list (array, vector), but not a string.

Python code below is more clear and easy to understand the procedure of this algorithm.

Code(C++):

class Solution {
public:
    string num2str(long a){
        if (a<0){a = -a;}
        ostringstream os;
        os << a;
        return os.str();
    }
    
    
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0 || denominator == 0){
            return "0";
        }
        bool pos=true;
        if ((numerator<0 && denominator>0)||(numerator>0 && denominator<0)){
            pos = false;
        }
        
        long numer = abs(numerator);
        long denom = abs(denominator);
        
        int l = -1;
        vector<string> res;
        int maxlen = 1000;
        vector<string> mod;
        
        while (mod.size()<maxlen){
            res.push_back(num2str(numer / denom));
            long m = numer % denom;
            if (m == 0){
                break;
            }
            
            for (int i=0;i<mod.size();i++){
                if (mod[i] == num2str(m)){
                    l = i;
                    break;
                }
            }
   
            if (l == -1){
                mod.push_back(num2str(m));
                numer = m * 10;
            }else{
                break;
            }
        }
        
        
        string r = "";
        
        if (res.size()==1){
            r = res[0];
        }else{
            r=res[0]+".";
            for (int i=1;i<res.size();i++){
                if (i == l+1){
                    r += "(";
                }
                r += res[i];
            }
            if (l != -1){
                r += ")";
            }
        }
        
        
        if (pos) {
            return r;
        }else{
            return "-"+r;
        }
    }
};

Code(Python):

class Solution:
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        if numerator * denominator < 0:
            pos = False
        else:
            pos = True
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        maxlen=1000
        mod = []
        if numerator == 0 or denominator == 0:
            return "0"
        res = []
        l = -1
        while len(mod) < maxlen:
            res.append(numerator/denominator)
            m = numerator % denominator
            if m == 0:
                break
            if m in mod:
                l = mod.index(m)
                break
            else:
                mod.append(m)
                numerator = m * 10
        
        if len(res) == 1:
            s = str(res[0])
        else:
            s = str(res[0]) + "."
            if l == -1:
                s = s + "".join([str(n) for n in res[1::]] )
            else:
                s = s+ "".join([str(n) for n in res[1:l+1]]) + "(" + "".join([str(n) for n in res[l+1::]]) + ")"
        if pos:
            return s
        else:
            return "-"+s