หาพาลินโดรมที่ใกล้ที่สุด (Find the Closest Palindrome) ใน C++

ภาพรวมปัญหา

กำหนดตัวเลข n (เป็นสตริง) หาพาลินโดรมที่ใกล้ที่สุด (ความต่างสัมบูรณ์น้อยที่สุด) อาจน้อยกว่าหรือมากกว่าก็ได้

ตัวอย่าง

n = "145" → Output: "141" (|145-141|=4, |151-145|=6)

แนวทางแก้ปัญหา

• สร้าง candidate palindromes จาก:
  1. 10^n - 1 (999...), 10^(n-1) - 1 (99...), 10^(n-1) + 1 (100...001), 10^n + 1 (100...001)
  2. ครึ่งหน้าของ n (half_val), half_val-1, half_val+1 สร้าง palindrome โดย mirror
• เรียง candidates, หาตัวที่ต่างจาก n และ diff น้อยสุด

ตัวอย่างโปรแกรม

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

class Solution {
public:
    string nearestPalindromic(string n) {
        int sn = n.size();
        if(sn == 1) return string(1, --n[0]);
        
        int half_sn = (sn + 1) / 2;
        long half_val = stol(n.substr(0, half_sn));
        
        vector<long> candidates = {pow(10, sn) - 1, pow(10, sn - 1) - 1, 
                                    pow(10, sn - 1) + 1, pow(10, sn) + 1};
        vector<long> fmdc = {half_val, half_val - 1, half_val + 1};
        
        for(long c : fmdc) {
            string rev = to_string(c);
            if(sn % 2) rev.pop_back();
            reverse(rev.begin(), rev.end());
            candidates.push_back(stol(to_string(c) + rev));
        }
        
        sort(candidates.begin(), candidates.end());
        string ans;
        long val = stol(n), min_diff = LONG_MAX;
        
        for(long candidate : candidates) {
            if(candidate == val) continue;
            long diff = labs(candidate - val);
            if(diff < min_diff) {
                min_diff = diff;
                ans = to_string(candidate);
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << (ob.nearestPalindromic("145"));
}

Input

"145"

Output

141