Find the Closest Palindrome: หา Palindrome ใกล้ที่สุดใน C++

ปัญหา

กำหนดตัวเลข n (เป็นสตริง) หา Palindrome ที่ ใกล้ที่สุด (Absolute Difference น้อยที่สุด) หากเท่ากันเลือกตัวเล็กกว่า ไม่รวมตัวมันเอง

ตัวอย่าง: "145" → "141" (diff=4) ใกล้กว่า "151" (diff=6)

แนวคิด: Candidate Generation

Palindrome ใกล้ที่สุดต้องอยู่ในกลุ่ม Candidate เหล่านี้:

1. Edge cases: 10^len - 1 (999...), 10^(len-1) - 1 (99...), 10^(len-1) + 1 (100...001), 10^len + 1 (100...001)
2. Mirror from half: นำครึ่งหน้ามา Mirror → Palindrome
3. Half ± 1: ครึ่งหน้าบวก/ลบ 1 แล้ว Mirror (จัดการ carry/borrow)

อัลกอริทึม

1. ถ้าความยาว 1: คืน n-1
2. คำนวณ half_len = (len + 1) / 2, half_val = ครึ่งหน้าตัวเลข
3. สร้าง Candidates:
   • Edge cases 4 ตัว
   • จาก half_val, half_val-1, half_val+1 → Mirror สร้าง Palindrome
4. Sort Candidates, หาตัวที่ |cand - val| น้อยที่สุด (ข้ามตัวเอง)

โค้ด C++

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

class Solution {
public:
    string nearestPalindromic(string n) {
        int len = n.size();
        if (len == 1) {
            return string(1, char(n[0] - 1));
        }
        
        int half_len = (len + 1) / 2;
        long half_val = stol(n.substr(0, half_len));
        
        vector<long> candidates = {
            (long)pow(10, len) - 1,       // 999...
            (long)pow(10, len - 1) - 1,   // 99...
            (long)pow(10, len - 1) + 1,   // 100...001
            (long)pow(10, len) + 1        // 100...001 (len+1 digits)
        };
        
        vector<long> halfs = {half_val, half_val - 1, half_val + 1};
        for (long h : halfs) {
            string s = to_string(h);
            string rev = s;
            if (len % 2) rev.pop_back();  // คี่: ตัดตัวกลางทิ้ง
            reverse(rev.begin(), rev.end());
            candidates.push_back(stol(s + rev));
        }
        
        sort(candidates.begin(), candidates.end());
        
        long val = stol(n);
        long best = -1, min_diff = LLONG_MAX;
        
        for (long cand : candidates) {
            if (cand == val) continue;
            long diff = labs(cand - val);
            if (diff < min_diff) {
                min_diff = diff;
                best = cand;
            }
        }
        return to_string(best);
    }
};

int main() {
    Solution ob;
    cout << ob.nearestPalindromic("145");  // 141
    return 0;
}

ตัวอย่าง Candidates สำหรับ "145"

ความซับซ้อน

• Time: O(len) - สร้าง Candidates คงที่ 7 ตัว
• Space: O(1)

Input / Output

Input:  "145"
Output: "141"