Найдите K-е наименьшее число палиндрома нечетной длины

Для заданного положительного целого числа K задача состоит в том, чтобы найти K ^-е наименьшее палиндромное число нечетной длины.

Примеры:

Input: K = 5
Output: 5
Explanation:
The palindromic numbers of odd lengths is {1, 2, 3, 4, 5, 6, 7, …, }. The 5^th smallest palindromic numbers is 5.

Input: K = 10
Output: 101

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Первые палиндромные числа длины 1 — это 1, 2, 3, 4, 5, 6, 7, 8 и 9.
• Первое палиндромное число длины 3 равно 101, что является 10-м наименьшим палиндромным числом нечетной длины. Точно так же 11 ^-е , 12 ^-е , 13 ^-е , …, 99 ^-е наименьшие палиндромные числа равны 111, 121, 131 …, 999 соответственно.
• Следовательно, K ^-е наименьшее число-палиндром нечетной длины может быть образовано путем соединения K и обратной стороны K , кроме последней цифры.

Из приведенных выше наблюдений K -е наименьшее палиндромное число нечетной длины получается путем добавления всех цифр числа K , кроме последней, стоящей в конце числа K .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log ₁₀ K)
Вспомогательное пространство: O(1)