C++で数値に最も近い回文数を求めるアルゴリズムと実装例

問題の概要

ある数値 n が与えられたとき、それに最も近い回文数（前から読んでも後ろから読んでも同じ並びになる数）を求める問題を考えます。「近さ」は絶対差で評価し、n より小さい回文でも大きい回文でも、差がより小さい方を採用します。

たとえば入力が 145 の場合を考えてみましょう。
下側の回文 141 との差は 4、上側の回文 151 との差は 6 です。差がより小さいのは 141 なので、答えは 141 になります。

解法の方針

すべての数を順番に調べて回文かどうか判定する方法は非効率です。そこで、「最も近い回文となり得る候補」だけを少数ピックアップして比較します。候補となるのは次のパターンです。

• n の前半部分をそのまま鏡写し（ミラー）にした数
• 前半部分に −1 / +1 した値を鏡写しにした数（繰り上がり・繰り下がりへの対応）
• 999…9（すべて 9）や 100…001 のような、桁数が変わる境界にある回文

これらの候補の中から n 自身を除き、絶対差が最小のものを選べば必ず正解に到達できます。

アルゴリズムの手順

1. sn := 文字列 n の長さとする
2. sn が 1 の場合、n[0] を 1 減らした文字からなる長さ 1 の文字列を返す（1桁なら答えは一意に決まるため）
3. half_sn := (sn + 1) / 2
4. half_val := n の先頭から half_sn 文字を取り出し、long 型の整数に変換する
5. 候補配列 candidates = { 10^sn − 1, 10^(sn−1) − 1, 10^(sn−1) + 1, 10^sn + 1 } を定義する
6. 配列 fmdc = { half_val, half_val − 1, half_val + 1 } を定義する
7. fmdc の各要素 c に対して以下を実行する：
   　rev := c を文字列化する
   　sn が奇数なら rev の末尾の 1 文字を削除する（中央の桁を二重にしないため）
   　rev を反転する
   　(c の文字列 + rev) を整数化して candidates に追加する
8. candidates をソートする
9. val := n を long 型に変換し、min_diff を十分大きな値で初期化する
10. candidates の各候補について以下を判定する：
    　候補が val と等しければスキップする（自分自身は対象外）
    　diff := |candidate − val| を計算する
    　diff < min_diff であれば min_diff と ans を更新する
11. ans を返す

具体例：「145」の場合の候補生成

sn = 3、half_sn = 2、half_val = 14 となります。fmdc = {14, 13, 15} からは、鏡写しによって 141、131、151 が生成されます。さらに固定候補として 9999、99、101、10001 が加わります。これらを val = 145 と比較すると、141 との差 4 が最小となるため、答えは 141 です。

C++ 実装例

以下が実際の実装コードです。

#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

計算量とまとめ

候補は常に高々 7 個（固定の 4 個 ＋ fmdc 由来の 3 個）しか存在しないため、ソートや比較にかかるコストは定数時間です。全体の計算量は文字列変換が支配的となり、入力の桁数を L とすると O(L) 程度で済みます。全数を総当たりで調べる方法と比べて大幅に高速であり、非常に大きな桁数の入力にも対応できるのがこの手法の強みです。

なお、実運用では pow 関数が浮動小数点数を返す点に注意が必要です。桁数が大きくなると精度誤差が生じうるため、10 のべき乗を整数演算で自前計算しておくとより安全です。