lc 166. fraction to recurring decimal

Description

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”
Example 2:

Input: numerator = 2, denominator = 1
Output: “2”
Example 3:

Input: numerator = 2, denominator = 3
Output: “0.(6)”


It’s a math problem, and why is it a medium?

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 {
public:
string fractionToDecimal(int numerator, int denominator) {
map<int, int> ndMap;
string res = "";
if(numerator < 0 ^ denominator < 0)
res += "-";
if(numerator == 0)
res = "";
long num = abs((long)numerator);
long den = abs((long)denominator);
long rem = num % den;
string decRes = "";
while((rem != 0) && ndMap.find(rem) == ndMap.end()){
ndMap[rem] = decRes.length();
rem *= 10;
decRes += to_string(rem / den);
rem %= den;
}
cout << decRes << endl;
if(rem == 0){
res += num % den == 0 ? to_string(num / den) : to_string(num / den) + "." + decRes;
}else
res += to_string(num / den) + "." + decRes.substr(0, ndMap[rem]) + "(" + decRes.substr(ndMap[rem]) + ")";
return res;
}
};

Original algorithm

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
string fractionToDecimal(int numr, int denr)
{
string res; // Initialize result

// Create a map to store already seen remainders
// remainder is used as key and its position in
// result is stored as value. Note that we need
// position for cases like 1/6. In this case,
// the recurring sequence doesn't start from first
// remainder.
map<int, int> mp;
mp.clear();

// Find first remainder
int rem = numr%denr;

// Keep finding remainder until either remainder
// becomes 0 or repeats
while ( (rem!=0) && (mp.find(rem) == mp.end()) )
{
// Store this remainder
mp[rem] = res.length();

// Multiply remainder with 10
rem = rem*10;

// Append rem / denr to result
int res_part = rem / denr;
res += to_string(res_part);

// Update remainder
rem = rem % denr;
}

return (rem == 0)? "" : res.substr(mp[rem]);
}