C++でのK桁のN番目の回文

k桁のn番目の回文を見つけるには、最初のk桁の番号から、n番目の回文番号が見つかるまで繰り返すことができます。このアプローチは効率的ではありません。自分で試すことができます。

それでは、k桁のn番目の回文を見つけるための効率的なアプローチを見てみましょう。

数字には2つの半分があります。前半は後半の逆に等しい。

k桁のn番目の数字の前半は

kが奇数の場合、（n-1）+ 10 ^{k / 2} else（n-1）+10 ^{k / 2-1}

k桁のn番目の数値の後半は、前半の桁の逆になります。 kが奇数の場合は、数値の前半の最後の桁を切り捨てます。

アルゴリズム

• 番号nとkを初期化します。
• kの値を使用して、k桁の回文の前半の長さを見つけます。
• 回文の前半はpow（10、length）+n-1です。
• kが奇数の場合は、回文の前半から最後の桁を削除します。
• 前半を反転して後半を印刷します。

実装

以下は、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;
}

出力

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

10066001