LeetCode daily problem P166 Fraction to Recurring Decimal

---

Timeline

Timeline

2025-09-24

init

High-precision division std::llabs

---

Problem:

P166 Fraction to Recurring Decimal

https://leetcode.cn/problems/fraction-to-recurring-decimal/description/?envType=daily-question&envId=2025-09-26

I used a simulation approach and finally managed to solve it after great effort. There are too many special cases. The best way is to use gdb to debug repeatedly to find the places not considered in the code and then improve it.
Note that you should not divide by the greatest common divisor first, because the time complexity of computing the greatest common divisor is higher than that of long division.
In addition, it is better to compute the integer part first, and then the fractional part. My solution did not consider this, which made the code a bit complicated.

#include <numeric>
#include <string>
#include <unordered_map>
#include <vector>

using std::string;
using std::unordered_map;
using std::vector;

class Solution {
public:
  string fractionToDecimal(int numerator, int denominator) {

    unsigned long long dividend;
    unsigned long long divisor;
    unsigned long long quotient;
    unsigned long long reminder;
    int dot = -1;
    int bracket = -1;
    // Record the result
    vector<int> res_vec;
    // Record each digit of the numerator
    vector<int> numerator_vec;
    // Record all dividends
    unordered_map<unsigned long long, unsigned long long> div_map;
    string res;
    int i = 0;
    int n;
    bool negative = false;

    // 0 divided by any number is 0
    if (numerator == 0) {
      return "0";
    }
    if ((numerator < 0 && denominator > 0) ||
        (numerator > 0 && denominator < 0)) {
      negative = true;
    }
    // The main reason for not using abs is that abs returns an unsigned int, which has a range problem.
    dividend = std::llabs((long long)numerator);
    divisor = std::llabs((long long)denominator);

    // First divide both by the greatest common divisor
    // n = std::gcd(dividend, divisor);
    // dividend /= n;
    // divisor /= n;

    // Put each digit of the numerator into numerator_vec
    while (dividend != 0) {
      numerator_vec.insert(numerator_vec.begin(), dividend % 10);
      dividend /= 10;
    }
    dividend = 0;
    // High-precision division

    // The first dividend
    n = numerator_vec.size();
    while (i < n && dividend < divisor) {
      dividend = dividend * 10 + numerator_vec[i];
      i++;
    }

    do {
      // Record the dividend
      if (div_map.find(dividend) != div_map.end() && dot > 0) { // Repeated
        bracket = div_map[dividend];                            // The repeated position
        break;
      } else {
        div_map[dividend] = res_vec.size();
      }
      // Quotient = dividend / divisor
      quotient = dividend / divisor;
      // Remainder = dividend / divisor
      reminder = dividend % divisor;
      res_vec.push_back(quotient);

      if (i < numerator_vec.size()) {
        dividend = reminder * 10 + numerator_vec[i];
        i++;
        reminder = 1; // Prevent exiting the loop
      } else {
        dividend = reminder * 10;
        if (dot < 0)
          dot = res_vec.size();
      }

    } while (reminder != 0);

    if (bracket >= 0 && dot > 0 && bracket < dot) {
      n = dot - bracket;
      for (i = 0; i < n; i++) {
        res_vec.push_back(res_vec[i + bracket]);
      }
      bracket = dot;
    }

    n = res_vec.size();
    // Build the string
    if (negative) {
      res += '-';
    }

    for (i = 0; i < n; i++) {
      if (i == dot) {
        res += '.';
      }
      if (i == bracket) {
        res += '(';
      }

      res += '0' + res_vec[i];
    }

    if (bracket > 0) {
      res += ')';
    }

    return res;
  }
};

int main() {
  Solution s;
  printf("%s\n", s.fractionToDecimal(420, 226).c_str());
  printf("%s\n", s.fractionToDecimal(-22, -2).c_str());
  printf("%s\n", s.fractionToDecimal(500, 10).c_str());
  printf("%s\n", s.fractionToDecimal(4, 333).c_str());
  printf("%s\n", s.fractionToDecimal(50, 8).c_str());
}

The official method also simulates long division, but the difference is that I recorded the dividend, while this solution records the remainder to determine whether a recurring decimal is produced.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = numerator;
        long denominatorLong = denominator;
        if (numeratorLong % denominatorLong == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans;
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans.push_back('-');
        }

        // Integer part
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        ans += to_string(integerPart);
        ans.push_back('.');

        // Fractional part
        string fractionPart;
        unordered_map<long, int> remainderIndexMap;
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.count(remainder)) {
            remainderIndexMap[remainder] = index;
            remainder *= 10;
            fractionPart += to_string(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // Has a repeating cycle
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};