C++でK桁のN番目の回文数を求める効率的なアルゴリズム

K桁のN番目の回文数を求めるには

K桁のN番目の回文数を求める場合、最初のK桁の数から順に1つずつ確認し、N番目の回文数が見つかるまで反復処理する方法が真っ先に思い浮かびます。しかし、この単純なアプローチは非常に非効率です。ぜひ一度ご自身でも試してみてください。

ここでは、K桁のN番目の回文数を効率的に求める方法を紹介します。

効率的なアプローチの考え方

回文数は「前半部分」と「後半部分」の2つに分けることができます。そして、前半部分の数字を逆順に並べ替えたものが後半部分と一致するという性質を持っています。つまり、前半部分さえ決まれば、回文全体が一意に定まるというわけです。

K桁のN番目の回文数の前半部分は、以下の式で求められます。

• kが奇数の場合：(n − 1) + 10^k/2
• kが偶数の場合：(n − 1) + 10^k/2−1

後半部分は、前半部分の数字を逆順に並べたものになります。ただし、kが奇数の場合は、前半部分の末尾の桁（中央の桁）を取り除いてから反転させる必要があります。

アルゴリズム

• 整数nとkを初期化します。
• kの値をもとに、K桁の回文数の前半部分の桁数を求めます。
• 回文数の前半部分は pow(10, length) + n − 1 として計算します。
• kが奇数の場合は、前半部分の末尾の桁を取り除きます。
• 前半部分を逆順に並べ替えて後半部分として出力します。

C++での実装

以下は、上記のアルゴリズムをC++で実装した例です。

#include<bits/stdc++.h>
using namespace std;
void findNthPalindrome(int n, int k) {
   int temp = (k & 1) ? (k / 2) : (k / 2 - 1);
   int palindrome = (int)pow(10, temp);
   palindrome += n - 1;
   cout << palindrome;
   if (k & 1) {
      palindrome /= 10;
   }
   while (palindrome) {
      cout << palindrome % 10;
      palindrome /= 10;
   }
      cout << endl;
}
int main(){
   int n = 7, k = 8;
   findNthPalindrome(n ,k);
   return 0;
}

コードのポイント

変数tempには、前半部分の桁数を決めるための値が格納されます。kが奇数の場合は k/2、偶数の場合は k/2 − 1 となります。これは、奇数桁の回文では中央の桁が前半側に含まれるためです。前半部分を出力した後、kが奇数であれば10で割って中央の桁を除外し、残りの桁を逆順に出力することで、完全な回文数を組み立てています。

実行結果

上記のコードを実行すると、次の出力が得られます。

10066001

例えば n = 7、k = 8 の場合、前半部分は 10³ + 7 − 1 = 1006 と計算されます。この「1006」と、それを反転した「6001」を連結すると、8桁の回文数「10066001」が得られるのです。このように、全ての候補を列挙せずとも、計算だけで目的の回文数を直接導き出すことができます。