Problem Source : https://leetcode-cn.com/problems/fraction-to-recurring-decimal/
Solution Source : https://github.com/hujingbo98/algorithm/blob/master/source/leetcode/0166_FractionToRecurringDecimal.cpp
166. Fraction to decimal
Given two integers representing the numerator and denominator of the fraction, return the decimal in the form of string.
If the decimal part is a circular decimal, enclose the circular part in parentheses.
If there are multiple answers, just return any one.
For all given inputs, ensure that the length of the answer string is less than 10 ^ 4.
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)"
Example 4:
Input: numerator = 4, denominator = 333 Output:"0.(012)"
Example 5:
Input: numerator = 1, denominator = 5 Output:"0.2"
Tips:
-2^31 <= numerator, denominator <= 2^31 - 1 denominator != 0
Method 1: long division + hash table
Convert fractions to integers or decimals by dividing the numerator and denominator. There are three possible results: integer, finite decimal and infinite circular decimal.
If the numerator can be divided by the denominator, the result is an integer. The quotient of the numerator divided by the denominator can be returned as a string.
If the numerator cannot be divided by the denominator, the result is a finite decimal or an infinite cyclic decimal, and the result needs to be calculated by simulating the long division method. In order to facilitate processing, first determine the positive and negative of the answer according to the positive and negative of the numerator and denominator (note that both the numerator and denominator are not 0 at this time), then turn both the numerator and denominator into positive numbers, and then calculate the long division.
When calculating the long division, first calculate the integer part of the result and splice the following parts into the result:
- If the result is negative, the minus sign is spliced into the result. If the result is positive, skip this step.
- Splices integer parts into the result.
- Splice decimal points into the result.
After the above splicing, calculate the decimal part according to the remainder.
When calculating the decimal part, multiply the remainder by 10 each time, then calculate the next digit of the decimal and get a new remainder. Repeat until the remainder is 0 or a circular section is found.
- If the remainder is 0, the result is a finite decimal.
- If a circular section is found, parentheses are inserted at the beginning and end of the circular section.
How do I find a circular section? For the same remainder, the next digit of the decimal must be the same. Therefore, if it is found that the remainder of a digit has appeared before in the calculation process, it is to find the circular section. In order to record whether each remainder has occurred, you need to use a hash table to store the subscript of each remainder for the first time in the decimal part.
Each time you get the remainder, judge whether it has appeared before it. If it has, add the left bracket at the first place and the right bracket at the end to return.
The time complexity is O(k), where k is the length of the result string. In this problem, K < = 10 ^ 4.
The spatial complexity is O(k). It is mainly the space used by the hash table. The hash table can store up to 10 ^ 4 key value pairs.
string fractionToDecimal(int numerator, int denominator) {
string ans;
long long numeratorLL = numerator;
long long denominatorLL = denominator;
if (0 == numeratorLL % denominatorLL)
return to_string(numeratorLL / denominatorLL);
if ((numeratorLL < 0) ^ (denominatorLL < 0))
ans.push_back('-');
numeratorLL = abs(numeratorLL);
denominatorLL = abs(denominatorLL);
int nbit = numeratorLL / denominatorLL;
ans.append(to_string(nbit));
long long nextNumeratorLL = numeratorLL % denominatorLL * 10;
ans.push_back('.');
unordered_map<long long, int> cache;
while (ans.length() < 10000 && 0 != nextNumeratorLL) {
auto it = cache.find(nextNumeratorLL);
if (it == cache.end()) {
cache.insert(std::pair(nextNumeratorLL, ans.length()));
} else {
ans.insert(it->second, 1, '(');
ans.push_back(')');
break;
}
nbit = nextNumeratorLL / denominatorLL;
ans.append(to_string(nbit));
nextNumeratorLL = nextNumeratorLL % denominatorLL * 10;
}
return ans;
}