Find Palindrome With Fixed Length

Problem

Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either thequeries[i]th smallestpositive palindrome of length intLength or -1 if no such palindrome exists.

A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

Examples

Example 1

Input: queries = [1,2,3,4,5,90], intLength = 3
Output: [101,111,121,131,141,999]
Explanation:
The first few palindromes of length 3 are:
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
The 90th palindrome of length 3 is 999.

Example 2

Input: queries = [2,4,6], intLength = 4
Output: [1111,1331,1551]
Explanation:
The first six palindromes of length 4 are:
1001, 1111, 1221, 1331, 1441, and 1551.

Constraints

• 1 <= queries.length <= 5 * 10^4
• 1 <= queries[i] <= 10^9
• 1 <= intLength <= 15

Solution

Method 1 – Construct Palindrome by Generating Half

Intuition

A palindrome is determined by its first half; the rest is a mirror. For a given length, we can generate the k-th palindrome by constructing the first half and reflecting it. This avoids generating all palindromes and is efficient even for large queries.

Approach

1. Calculate the number of digits in the first half: (intLength + 1) // 2.
2. The smallest first half is 10^(halfLen-1), since palindromes can't have leading zeros.
3. For each query:
   • The k-th palindrome's first half is smallest + queries[i] - 1.
   • If this exceeds the largest possible first half, return -1.
   • Otherwise, build the palindrome by mirroring the first half (excluding the last digit if length is odd).
4. Return the result for all queries.

Code

C++

class Solution {
public:
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        vector<long long> ans;
        int half = (intLength + 1) / 2;
        long long start = pow(10, half - 1);
        long long end = pow(10, half) - 1;
        for (int q : queries) {
            long long first = start + q - 1;
            if (first > end) {
                ans.push_back(-1);
                continue;
            }
            string s = to_string(first);
            string rev = s.substr(0, intLength / 2);
            reverse(rev.begin(), rev.end());
            ans.push_back(stoll(s + rev));
        }
        return ans;
    }
};

Go

func kthPalindrome(queries []int, intLength int) []int64 {
    ans := make([]int64, len(queries))
    half := (intLength + 1) / 2
    start := int64(1)
    for i := 1; i < half; i++ {
        start *= 10
    }
    end := start*10 - 1
    for i, q := range queries {
        first := start + int64(q) - 1
        if first > end {
            ans[i] = -1
            continue
        }
        s := fmt.Sprintf("%d", first)
        rev := ""
        for j := len(s) - 1 - intLength%2; j >= 0; j-- {
            rev += string(s[j])
        }
        res, _ := strconv.ParseInt(s+rev, 10, 64)
        ans[i] = res
    }
    return ans
}

Java

class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        int n = queries.length, half = (intLength + 1) / 2;
        long[] ans = new long[n];
        long start = (long)Math.pow(10, half - 1), end = (long)Math.pow(10, half) - 1;
        for (int i = 0; i < n; i++) {
            long first = start + queries[i] - 1;
            if (first > end) {
                ans[i] = -1;
                continue;
            }
            String s = Long.toString(first);
            StringBuilder rev = new StringBuilder(s.substring(0, intLength / 2)).reverse();
            ans[i] = Long.parseLong(s + rev);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun kthPalindrome(queries: IntArray, intLength: Int): LongArray {
        val half = (intLength + 1) / 2
        val start = Math.pow(10.0, (half - 1).toDouble()).toLong()
        val end = Math.pow(10.0, half.toDouble()).toLong() - 1
        return queries.map { q ->
            val first = start + q - 1
            if (first > end) -1L
            else {
                val s = first.toString()
                val rev = s.substring(0, intLength / 2).reversed()
                (s + rev).toLong()
            }
        }.toLongArray()
    }
}

Python

class Solution:
    def kthPalindrome(self, queries: list[int], intLength: int) -> list[int]:
        ans = []
        half = (intLength + 1) // 2
        start = 10 ** (half - 1)
        end = 10 ** half - 1
        for q in queries:
            first = start + q - 1
            if first > end:
                ans.append(-1)
                continue
            s = str(first)
            rev = s[:intLength // 2][::-1]
            ans.append(int(s + rev))
        return ans

Rust

impl Solution {
    pub fn kth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
        let half = (int_length + 1) / 2;
        let start = 10_i64.pow((half - 1) as u32);
        let end = 10_i64.pow(half as u32) - 1;
        queries.iter().map(|&q| {
            let first = start + q as i64 - 1;
            if first > end { -1 }
            else {
                let s = first.to_string();
                let rev: String = s.chars().take((int_length / 2) as usize).rev().collect();
                (s + &rev).parse().unwrap()
            }
        }).collect()
    }
}

TypeScript

class Solution {
    kthPalindrome(queries: number[], intLength: number): number[] {
        const ans: number[] = [];
        const half = Math.floor((intLength + 1) / 2);
        const start = Math.pow(10, half - 1);
        const end = Math.pow(10, half) - 1;
        for (const q of queries) {
            const first = start + q - 1;
            if (first > end) {
                ans.push(-1);
                continue;
            }
            const s = first.toString();
            const rev = s.slice(0, Math.floor(intLength / 2)).split('').reverse().join('');
            ans.push(Number(s + rev));
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(m), where m is the number of queries. Each query is processed in constant time.
• 🧺 Space complexity: O(m), for the output array.