## 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