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 method, tried my best and finally succeeded. There are too many special cases. It’s best to use gdb to debug step by step to find the parts not considered in the code and then improve.
Note: do not divide by the greatest common divisor first, because the time complexity of calculating the GCD is higher than that of long division.
Also, it’s better to calculate the integer part first, then the decimal part. My solution did not consider this, making 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 result
    vector<int> res_vec;
    // Record each digit of 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 range issues.
    dividend = std::llabs((long long)numerator);
    divisor = std::llabs((long long)denominator);

    // First divide both by the greatest common factor.
    // 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.

    // 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];                            // 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 if a repeating decimal occurs.

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('.');

        // Decimal 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 block
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};