首页 > 代码库 > LeetCode - Fraction to Recurring Decimal
LeetCode - Fraction to Recurring Decimal
Fraction to Recurring Decimal
2015.1.23 15:59
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)".
Solution:
First of all, the denominator won‘t be 0. Next you should take care of the sign first, + or -, make it positive.
3 % 5 == 3
5 % 3 == 2
6 % 3 == 0
The process of calculating a rational fraction is actually by division and modulus. If the remainder is zero, you get a finite fraction, otherwise an infinite loop. There‘s gonna be a loop as long as it is rational fraction. So, you‘ll have to record the remainder sequence, with a hash table maybe. When the same remainder is encountered, you know you‘ve found the loop sequence.
Also there‘s something to be careful about printing. Like the following.
5 / 3 == 1.(6)
0 / 3 == 0
6 / 3 == 2
1 / 7 == 0.(142857)
The denominator can be really large, so don‘t try to use an int A[MAXN] to record the sequence, it won‘t do. That‘s why I suggest hashing.
The time complexity is generally O(denominator), but should be much smaller in fact. The fraction 1 / n may have a loop sequence of at most n - 1 in length, but usually far shorter. Space complexity is the same scale.
Accepted code:
1 // 1RE, 1TLE, 3MLE, 1AC, watch out for boundary cases and memory limit 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 #include <unordered_map> 6 using namespace std; 7 8 typedef long long int ll; 9 10 class Solution {11 public:12 string fractionToDecimal(int numerator, int denominator) {13 ll n = numerator;14 ll d = denominator;15 16 int sn, sd;17 18 sn = n >= 0 ? 1 : -1;19 n = n >= 0 ? n : -n;20 sd = d >= 0 ? 1 : -1;21 d = d >= 0 ? d : -d;22 23 if (n == 0) {24 return "0";25 }26 27 string res = "";28 if (sn * sd < 0) {29 res.push_back(‘-‘);30 }31 32 ll q = n / d;33 ll r = n % d;34 35 res += to_string(q);36 37 if (r == 0) {38 return res;39 }40 41 res.push_back(‘.‘);42 int pos = (int)res.length();43 44 unordered_map<ll, int> seq;45 unordered_map<ll, int>::iterator it;46 47 while (r != 0) {48 it = seq.find(r);49 if (it != seq.end()) {50 res.insert(it->second, "(");51 res.push_back(‘)‘);52 return res;53 }54 seq[r] = pos;55 q = r * 10 / d;56 r = r * 10 % d;57 res.push_back((int)q + ‘0‘);58 ++pos;59 }60 61 seq.clear();62 return res;63 }64 private:65 };66 /*67 int main()68 {69 int n, d;70 Solution sol;71 72 while (cin >> n >> d) {73 cout << sol.fractionToDecimal(n, d) << endl;74 }75 76 return 0;77 }78 */
LeetCode - Fraction to Recurring Decimal