1class Solution {
2    public long[] kthPalindrome(int[] queries, int intLength) {
3        int queryCount = queries.length;
4        long[] result = new long[queryCount];
5      
6        // Calculate the length of the first half of the palindrome
7        // For odd length palindromes, we include the middle digit
8        int halfLength = (intLength + 1) >> 1;  // Equivalent to (intLength + 1) / 2
9      
10        // Calculate the range of valid first halves
11        long minHalf = (long) Math.pow(10, halfLength - 1);  // Smallest n-digit number
12        long maxHalf = (long) Math.pow(10, halfLength) - 1;  // Largest n-digit number
13      
14        // Process each query
15        for (int i = 0; i < queryCount; ++i) {
16            // Calculate the first half value for the k-th palindrome
17            // queries[i] is 1-indexed, so we subtract 1
18            long firstHalf = minHalf + queries[i] - 1;
19          
20            // Check if the requested palindrome exists
21            if (firstHalf > maxHalf) {
22                result[i] = -1;
23                continue;
24            }
25          
26            // Convert the first half to string
27            String halfString = "" + firstHalf;
28          
29            // Build the complete palindrome by appending the reversed half
30            // For odd length palindromes, skip the middle digit when reversing
31            String reversedPart = new StringBuilder(halfString)
32                .reverse()
33                .substring(intLength % 2);  // Skip first char if odd length
34          
35            // Combine both parts to form the complete palindrome
36            String palindrome = halfString + reversedPart;
37          
38            // Convert the palindrome string to long and store in result
39            result[i] = Long.parseLong(palindrome);
40        }
41      
42        return result;
43    }
44}
45

1class Solution {
2public:
3    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
4        // Calculate the length of the first half of the palindrome
5        // For odd length palindromes, we include the middle digit in the first half
6        int halfLength = (intLength + 1) >> 1;  // Equivalent to (intLength + 1) / 2
7      
8        // Calculate the range of possible values for the first half
9        // e.g., for halfLength = 3: start = 100, end = 999
10        long long startValue = pow(10, halfLength - 1);
11        long long endValue = pow(10, halfLength) - 1;
12      
13        vector<long long> result;
14      
15        // Process each query
16        for (int& query : queries) {
17            // Calculate the value of the first half for the k-th palindrome
18            // query is 1-indexed, so we subtract 1 to get 0-indexed position
19            long long firstHalfValue = startValue + query - 1;
20          
21            // Check if the requested palindrome exists
22            if (firstHalfValue > endValue) {
23                result.push_back(-1);
24                continue;
25            }
26          
27            // Convert the first half to string for manipulation
28            string firstHalf = to_string(firstHalfValue);
29          
30            // Create a copy for reversing
31            string reversedHalf = firstHalf;
32            reverse(reversedHalf.begin(), reversedHalf.end());
33          
34            // Build the complete palindrome
35            // For odd length: skip the middle digit when appending (already in firstHalf)
36            // For even length: append the entire reversed string
37            firstHalf += reversedHalf.substr(intLength % 2);
38          
39            // Convert the palindrome string back to long long and add to result
40            result.push_back(stoll(firstHalf));
41        }
42      
43        return result;
44    }
45};
46

1/**
2 * Finds the k-th palindrome number with a specific length for each query
3 * @param queries - Array of k values representing the k-th palindrome to find
4 * @param intLength - The desired length of palindrome numbers
5 * @returns Array of palindrome numbers corresponding to each query, or -1 if not exists
6 */
7function kthPalindrome(queries: number[], intLength: number): number[] {
8    // Determine if the palindrome length is odd
9    const isOddLength = intLength % 2 === 1;
10  
11    // Calculate the number of digits in the first half of the palindrome
12    // For odd length, we include the middle digit in the first half
13    const halfLength = Math.floor(intLength / 2) + (isOddLength ? 1 : 0);
14  
15    // Calculate the smallest number that forms the first half of palindrome
16    // e.g., for length 4 or 5, starts from 10; for length 6 or 7, starts from 100
17    const firstHalfStart = Math.pow(10, halfLength - 1);
18  
19    // Calculate the maximum number of palindromes possible with this length
20    // The first half can range from firstHalfStart to (firstHalfStart * 10 - 1)
21    const maxPalindromeCount = firstHalfStart * 9;
22  
23    // Process each query to find the corresponding palindrome
24    return queries.map(kthValue => {
25        // Check if the requested k-th palindrome exists
26        if (kthValue > maxPalindromeCount) {
27            return -1;
28        }
29      
30        // Calculate the first half of the k-th palindrome
31        const firstHalf = firstHalfStart + kthValue - 1;
32      
33        // Convert first half to string for manipulation
34        const firstHalfString = firstHalf.toString();
35      
36        // Create the second half by reversing the first half
37        // For odd length palindromes, skip the middle digit when creating the second half
38        const secondHalfString = firstHalfString
39            .split('')
40            .reverse()
41            .slice(isOddLength ? 1 : 0)
42            .join('');
43      
44        // Combine first half and second half to form the complete palindrome
45        const palindrome = Number(firstHalfString + secondHalfString);
46      
47        return palindrome;
48    });
49}
50