166. Fraction to Recurring Decimal

  • 17.1%

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.

1
2
3
4
5
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)".

Hint:

  1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
  2. Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
  3. Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

方法一:

一个基本经验是,如果数字特别长,一定要转成long long

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
string res;
if(numerator==0 || denominator==0) return to_string(0);
if(numerator<0&& denominator>0 || numerator>0&&denominator<0)
res = res + "-";
// 一个基本经验是,如果遇到数字可能会出现特别长的,一定要用long long
long long nu = abs((long long)numerator);
long long de = abs((long long)denominator);
res += to_string(nu/de);
if(nu%de==0)
return res;
res += ".";
unordered_map<int, int> map;
for(nu %= de; nu;nu %= de){
if(map.find(nu)!=map.end()){
res.insert(map[nu], "(");
res += ")";
break;
}
map[nu] = res.size();
nu *= 10;
res += to_string(nu/de);
}
return res;
}
};

https://discuss.leetcode.com/topic/6079/accepted-cpp-solution-with-explainations

Accepted cpp solution, with explainations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// upgraded parameter types
string fractionToDecimal(int64_t n, int64_t d) {
// zero numerator
if (n == 0) return "0";

string res;
// determine the sign
if (n < 0 ^ d < 0) res += '-';

// remove sign of operands
n = abs(n), d = abs(d);

// append integral part
res += to_string(n / d);

// in case no fractional part
if (n % d == 0) return res;

res += '.';

unordered_map<int, int> map;

// simulate the division process
for (int64_t r = n % d; r; r %= d) {

// meet a known remainder
// so we reach the end of the repeating part
if (map.count(r) > 0) {
res.insert(map[r], 1, '(');
res += ')';
break;
}

// the remainder is first seen
// remember the current position for it
map[r] = res.size();

r *= 10;

// append the quotient digit
res += to_string(r / d);
}

return res;
}

https://discuss.leetcode.com/topic/17071/0ms-c-solution-with-detailed-explanations

0ms C++ Solution with Detailed Explanations

Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a ). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.

Now we have solved the trickiest part of this problem.

There are some remaining problems to solve to achieve a bug-free solution.

  1. Pay attention to the sign of the result;
  2. Handle cases that may cause overflow like numerator = -2147483648, denominator = -1 appropriately by using long long;
  3. Handle all the cases of (1) no fractional part; (2) fractional part does not recur; and (3) fractional part recurs respectively.

To handle problem 3, we divide the division process into the integral part and the fractional part. For the fractional part, if it does not recur, then the remainder will become 0 at some point and we could return. If it does recur, the method metioned in the first paragraph has already handled it.

Taking all these into considerations, we have the following code, which takes 0 ms :-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (!numerator) return "0";
string res;
if (numerator < 0 ^ denominator < 0) res += '-';
long numer = numerator < 0 ? (long)numerator * (-1) : (long)numerator;
long denom = denominator < 0 ? (long)denominator * (-1) : (long)denominator;
long integral = numer / denom;
res += to_string(integral);
long rmd = numer % denom;
if (!rmd) return res;
res += '.';
rmd *= 10;
unordered_map<long, long> mp;
while (rmd) {
long quotient = rmd / denom;
if (mp.find(rmd) != mp.end()) {
res.insert(mp[rmd], 1, '(');
res += ')';
break;
}
mp[rmd] = res.size();
res += to_string(quotient);
rmd = (rmd % denom) * 10;
}
return res;
}
};

https://discuss.leetcode.com/topic/7699/do-not-use-python-as-cpp-here-s-a-short-version-python-code

Do not use python as cpp, here’s a short version python code

Though python is slow, It is easy to write

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
# @return a string
def fractionToDecimal(self, numerator, denominator):
n, remainder = divmod(abs(numerator), abs(denominator))
sign = '-' if numerator*denominator < 0 else ''
result = [sign+str(n), '.']
stack = []
while remainder not in stack:
stack.append(remainder)
n, remainder = divmod(remainder*10, abs(denominator))
result.append(str(n))

idx = stack.index(remainder)
result.insert(idx+2, '(')
result.append(')')
return ''.join(result).replace('(0)', '').rstrip('.')

and there’s no overflow


https://discuss.leetcode.com/topic/9778/python-solution

Python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
# @return a string
def fractionToDecimal(self, numerator, denominator):
res=""
if numerator/denominator<0:
res+="-"
elif numerator%denominator==0:
return str(numerator/denominator)
numerator=abs(numerator)
denominator=abs(denominator)
res+=str(numerator/denominator)
res+="."
numerator%=denominator
i=len(res)
table={}
while numerator!=0:
if numerator not in table.keys():
table[numerator]=i
else:
i=table[numerator]
res=res[:i]+"("+res[i:]+")"
return res
numerator=numerator*10
res+=str(numerator/denominator)
numerator%=denominator
i+=1
return res

Idea is to put every remainder into the hash table as a key, and the current length of the result string as the value. When the same remainder shows again, it’s circulating from the index of the value in the table.

谢谢你,可爱的朋友。