মনে করুন, একটি সংখ্যা n দেওয়া আছে। এর সবচেয়ে কাছের প্যালিনড্রোম সংখ্যা বের করতে হবে। প্যালিনড্রোমটি n-এর চেয়ে ছোট বা বড় হতে পারে, которомান অ্যাবসোলিউট ডিফারেন্স ন্যূনতম হবে।
যেমন, n = 145 হলে, ফলাফল ১৪১।
সমাধানের ধাপসমূহ
- sn := n.size()
- যদি sn == 1 হয়, n[0]-- করে স্ট্রিং রিটার্ন
- half_sn := (sn+1)/2, half_val := stol(n.substr(0, half_sn))
- ক্যান্ডিডেট অ্যারে: 10^sn-1, 10^(sn-1)-1, 10^(sn-1)+1, 10^sn+1
- fmdc অ্যারে: half_val, half_val-1, half_val+1
- প্রতিটি c ∈ fmdc এর জন্য:
- rev := c-এর স্ট্রিং, sn বিজোড় হলে শেষ ক্যারেক্টার মুছে দিন
- rev রিভার্স করুন, c+rev কে ক্যান্ডিডেটে যোগ করুন
- ক্যান্ডিডেট সর্ট করুন
- val := n ইন্টিজারে, min_diff := INT_MAX
- প্রতিটি ক্যান্ডিডেটের জন্য:
- যদি ক্যান্ডিডেট == val হয়, স্কিপ করুন
- diff := |candidate - val|, যদি diff < min_diff হয়, আপডেট করুন
- ans রিটার্ন করুন
উদাহরণ
#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 = INT_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; } }; main(){ Solution ob; cout << (ob.nearestPalindromic("145")); }
ইনপুট
"145"
আউটপুট
141
