To simplify casework, consider the following problem:

• What is the \(N\)-th smallest positive palindrome number?

(Solving this immediately solves the original problem.)

Let us enumerate the number of palindromes with a certain number of digits:

• \(1\)-digit palindrome numbers: \(1, 2, 3, \dots, 9\), there are \(9\) of them.
• \(2\)-digit palindrome numbers: \(11, 22, 33, \dots, 99\), there are \(9\) of them.
• \(3\)-digit palindrome numbers: \(111, 121, 131, \dots, 999\), there are \(90\) of them.
• \(4\)-digit palindrome numbers: \(1111, 1221, 1331, \dots, 9999\), there are \(90\) of them.
• \(\vdots\)

One can guess the pattern by staring at the enumerated palindrome numbers as follows:

• If \(d\) is odd, the most significant \((d+1)/2\) digits of the \(d\)-digit palindrome numbers comprises \(((d+1)/2)\)-digit positive integers.
  • For example, the \(3\)-digit palindrome numbers have two significant digits as follows: \(11, 12, 13, \dots, 99\).
• If \(d\) is even, the most significant \(d/2\) digits of the \(d\)-digit palindrome numbers comprises \((d/2)\)-digit positive integers.
  • For example, the \(5\)-digit palindrome numbers have two significant digits as follows: \(11, 12, 13, \dots, 99\).

Using this fact, it turns out that a \(d\)-digit palindrome number has the following properties:

• For \(x = \lfloor (d+1)/2 \rfloor\), the following two propositions hold:
  • There are \(9 \times 10^{x-1}\) palindrome numbers with \(d\) digits.
  • The \(x\) most significant digits of the \(k\)-th smallest palindrome number with \(d\) digits form an integer \(10^{x-1} + k - 1\)

By the observation above, one can obtain the \(N\)-th smallest palindrome numbers as follows.

• For \(d = 1, 2, \dots \), do the following.
  • Let \(x = \lfloor (d + 1) / 2 \rfloor\).
  • Check if \(N \leq 9 \times 10^{x - 1}\).
    • If \(N \leq 9 \times 10^{x - 1}\), the sought palindrome number turns out to have \(d\) digits. Compute \(y = 10^{x-1} + N - 1\), and print the \(d\)-digit palindrome number staring with \(y\). Break the loop with respect to \(d\).
    • Otherwise, the sough palindrome number has more than \(d\) digits. Subtract \(9 \times 10^{x-1}\) from \(N\).

The complexity is \(\mathrm{O}(\log N)\), which is fast enough. Note that the sought palindrome number can have as large as \(35\) digits, so avoid using a fixed-width integer type such as long long in C++ as it may cause an overflow. (Using a string type or a bigint helps circumventing the issue.)

Sample code (C++)

#include <iostream>
#include <string>
using namespace std;

long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }

int main() {
  long long N;
  cin >> N;
  if (N == 1) {
    cout << 0 << endl;
    return 0;
  }
  N--;
  for (int d = 1;; d++) {
    int x = (d + 1) / 2;
    if (N <= 9 * TEN(x - 1)) {
      string S = to_string(TEN(x - 1) + N - 1);
      S.resize(d, ' ');
      for (int i = x; i < d; i++) S[i] = S[d - 1 - i];
      cout << S << endl;
      return 0;
    } else {
      N -= 9 * TEN(x - 1);
    }
  }
}