Problem Description

You are given two integers intLength and k. Your task is to find the k-th smallest positive palindrome of length intLength.

• A palindrome is a number that reads the same backward as forward (e.g., 121, 1331).
• The palindrome must be exactly intLength digits long (no leading zeros).
• If there is no such palindrome (i.e., there are fewer than k palindromes of this length), return -1.

Constraints:

• 1 ≤ intLength ≤ 15
• 1 ≤ k ≤ 10⁹

Thought Process

At first glance, it might seem tempting to generate all palindromes of the given length, sort them, and pick the k-th one. However, this would be far too slow, especially for large values of intLength and k. For example, for intLength = 15, there could be millions or billions of palindromes!

Instead, we should look for a way to directly compute the k-th palindrome without generating all possible palindromes. The key insight is that palindromes of a given length can be constructed by mirroring the first half of the number. This means there is a direct relationship between the k-th palindrome and its first half.

Solution Approach

Let's break down the optimized solution step by step:

1. Understanding Palindrome Structure:
   • For a palindrome of length n, the first (n+1)//2 digits determine the whole number.
   • For example, for length 5, the first 3 digits (say, "abc") define the palindrome as "abcba".
2. Counting Palindromes:
   • The count of palindromes is 9 * 10^{(n-1)//2} because the first digit cannot be zero (must be 1-9), and the remaining digits can be 0-9.
3. Finding the k-th Palindrome:
   • We can directly compute the first half by adding k-1 to the smallest possible first half (which starts at 10^{(half_length-1)}).
   • If k is too large (i.e., the resulting first half overflows the possible range), return -1.
4. Constructing the Full Palindrome:
   • For odd lengths, exclude the last digit of the first half when mirroring.
   • For even lengths, mirror the entire first half.

This approach gives us a direct formula to compute the k-th palindrome, making the solution efficient even for large inputs.

Example Walkthrough

Let's walk through an example with intLength = 5 and k = 4:

1. The first half length is (5 + 1) // 2 = 3.
2. The smallest possible first half is 100 (since leading zeros are not allowed).
3. To get the 4th palindrome, add k-1 = 3 to 100, giving 103.
4. Now, construct the full palindrome:
   • First half: "103"
   • Since the length is odd, mirror "10" (exclude last digit): "10"
   • Full palindrome: "103" + "10" reversed = "10301"
5. So, the answer is 10301.

Time and Space Complexity

• Brute-force Approach:
  • Time: O(N), where N is the number of palindromes of length intLength (can be up to 9 * 10⁷ for large lengths).
  • Space: O(1) if generating palindromes one by one, but O(N) if storing them.
• Optimized Approach (This Solution):
  • Time: O(L), where L is intLength (for string manipulation and mirroring).
  • Space: O(L) for constructing the palindrome string.

The optimized approach is extremely efficient and suitable for the given constraints.

Summary

To find the k-th palindrome of a given length, we leverage the fact that palindromes are determined by their first half. By directly computing the k-th possible first half and mirroring it, we can efficiently construct the desired palindrome in O(L) time, where L is the length of the palindrome. This avoids any need for brute-force generation and works even for very large inputs.

Code Implementation

class Solution:
    def kthPalindrome(self, queries, intLength):
        res = []
        half_len = (intLength + 1) // 2
        start = 10 ** (half_len - 1)
        for k in queries:
            half = start + k - 1
            if len(str(half)) > half_len:
                res.append(-1)
                continue
            half_str = str(half)
            if intLength % 2 == 0:
                pal = half_str + half_str[::-1]
            else:
                pal = half_str + half_str[:-1][::-1]
            res.append(int(pal))
        return res
      

class Solution {
public:
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        vector<long long> res;
        int half_len = (intLength + 1) / 2;
        long long start = pow(10, half_len - 1);
        for (int k : queries) {
            long long half = start + k - 1;
            if (to_string(half).length() > half_len) {
                res.push_back(-1);
                continue;
            }
            string half_str = to_string(half);
            string pal = half_str;
            if (intLength % 2 == 0) {
                reverse(half_str.begin(), half_str.end());
                pal += half_str;
            } else {
                string rev = half_str.substr(0, half_len - 1);
                reverse(rev.begin(), rev.end());
                pal += rev;
            }
            res.push_back(stoll(pal));
        }
        return res;
    }
};
      

class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] res = new long[queries.length];
        int halfLen = (intLength + 1) / 2;
        long start = (long)Math.pow(10, halfLen - 1);
        for (int i = 0; i < queries.length; i++) {
            long half = start + queries[i] - 1;
            if (String.valueOf(half).length() > halfLen) {
                res[i] = -1;
                continue;
            }
            String halfStr = String.valueOf(half);
            StringBuilder pal = new StringBuilder(halfStr);
            if (intLength % 2 == 0) {
                pal.append(new StringBuilder(halfStr).reverse());
            } else {
                pal.append(new StringBuilder(halfStr.substring(0, halfLen - 1)).reverse());
            }
            res[i] = Long.parseLong(pal.toString());
        }
        return res;
    }
}
      

var kthPalindrome = function(queries, intLength) {
    let res = [];
    let halfLen = Math.floor((intLength + 1) / 2);
    let start = Math.pow(10, halfLen - 1);
    for (let k of queries) {
        let half = start + k - 1;
        if (half.toString().length > halfLen) {
            res.push(-1);
            continue;
        }
        let halfStr = half.toString();
        let pal;
        if (intLength % 2 === 0) {
            pal = halfStr + halfStr.split('').reverse().join('');
        } else {
            pal = halfStr + halfStr.slice(0, halfLen - 1).split('').reverse().join('');
        }
        res.push(Number(pal));
    }
    return res;
};