Sponsored
Sponsored
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
1#include <string>
2#include <unordered_map>
3
4class Solution {
5public:
6 std::string fractionToDecimal(int numerator, int denominator) {
7 if (numerator == 0) return "0";
8 std::string result;
9 if ((numerator < 0) ^ (denominator < 0)) result += "-";
10 long num = std::labs(numerator);
11 long den = std::labs(denominator);
12 result += std::to_string(num / den);
13 long remainder = num % den;
14 if (remainder == 0) return result;
15 result += ".";
16 std::unordered_map<long, int> map;
17 while (remainder) {
18 if (map.find(remainder) != map.end()) {
19 result.insert(map[remainder], "(");
20 result += ")";
21 break;
22 }
23 map[remainder] = result.size();
24 remainder *= 10;
25 result += std::to_string(remainder / den);
26 remainder %= den;
27 }
28 return result;
29 }
30};This C++ solution follows similar logic as Python and Java versions. It uses an unordered_map to track the remainders and their respective positions. If the remainder repeats, it indicates a repeating sequence of decimal places, which are enclosed in parentheses.
The solution efficiently handles negative values and zero remainders using helper functions from the standard library.