เศษส่วนเป็นทศนิยมซ้ำ (Fraction to Recurring Decimal) ใน C++

เศษส่วนเป็นทศนิยมซ้ำ (Fraction to Recurring Decimal)

ให้ตัวเศษและตัวส่วนเป็นจำนวนเต็ม แปลงเป็นสตริงทศนิยม ถ้าส่วนทศนิยมซ้ำ ให้ครอบส่วนที่ซ้ำด้วยวงเล็บ

ตัวอย่าง: 2/3 → "0.(6)", 100/6 → "16.(6)"

ขั้นตอนการแก้ปัญหา (Long Division + Hash Map)

1. ถ้าตัวเศษ 0 คืนค่า "0"
2. จัดการเครื่องหมายลบ
3. คำนวณส่วนจำนวนเต็ม divisor / dividend
4. คำนวณเศษ remainder = divisor % dividend
5. ถ้าเศษ 0 คืนค่าส่วนจำนวนเต็ม
6. เพิ่มจุดทศนิยม '.', ใช้ map remainder -> position
7. วนในขณะที่ remainder != 0:
   • ถ้าเจอ remainder ซ้ำใน map: แทรก '(' ที่ตำแหน่งเก่า, เพิ่ม ')' ท้าย, break
   • บันทึกตำแหน่งปัจจุบันของ remainder
   • remainder *= 10, เพิ่ม remainder / dividend เป็นหลักทศนิยม
   • remainder %= dividend

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string ans;
        if ((numerator < 0) ^ (denominator < 0)) ans += '-';
        long n = labs(numerator), d = labs(denominator);
        ans += to_string(n / d);
        long rem = n % d;
        if (rem == 0) return ans;
        ans += '.';
        unordered_map<long, int> pos;
        while (rem != 0) {
            if (pos.count(rem)) {
                ans.insert(pos[rem], "(");
                ans += ')';
                break;
            }
            pos[rem] = ans.size();
            rem *= 10;
            ans += to_string(rem / d);
            rem %= d;
        }
        return ans;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: 100 6

Output: 16.(6)