# Find Palindrome With Fixed Length
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-palindrome-with-fixed-length)
Canonical: https://scaleengineer.com/dsa/problems/find-palindrome-with-fixed-length
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [VMware](https://scaleengineer.com/companies/vmware)
---
## Problem
Given an integer array `queries` and a **positive** integer `intLength`, return _an array_ `answer` _where_ `answer[i]` _is either the_ `queries[i]th` _smallest **positive 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.

**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 * 104`
* `1 <= queries[i] <= 109`
* `1 <= intLength <= 15`

# Approaches
## Brute Force by Iteration and Checking
This naive approach involves generating and checking numbers one by one. For each query, it iterates through all numbers of the specified length, tests each for the palindrome property, and keeps a count. When the count matches the query number, the corresponding palindrome is found.
**Time:** O(10^L * L + Q), where L is `intLength` and Q is the number of queries. The term `10^L * L` comes from iterating through all numbers of length L and checking if they are palindromes. This is prohibitively slow for the given constraints. · **Space:** O(N + P), where N is the number of queries and P is the total number of palindromes of `intLength`. In the worst case (`intLength=15`), P can be up to `9 * 10^7`, leading to high memory usage.
**Pros:** Simple to conceptualize and implement.; Requires minimal mathematical insight.
**Cons:** Extremely inefficient and slow.; Will result in a 'Time Limit Exceeded' error on any reasonably large test case due to the nested loops and large search space.; Repeats the same palindrome generation work for each query.
### Explanation
The brute-force method directly simulates the process of finding the k-th palindrome. It starts from the smallest positive number of `intLength` and iterates upwards. In each step, it checks if the current number is a palindrome. A counter is maintained to track how many palindromes have been found. When this counter reaches the value specified by a query, the current number is the answer for that query. This entire process is repeated for every single query in the input array.

For example, to find the 3rd palindrome of length 3:
1. Start with 100. Is it a palindrome? No.
2. 101. Is it a palindrome? Yes. Count = 1.
3. 102...110. No.
4. 111. Is it a palindrome? Yes. Count = 2.
5. 112...120. No.
6. 121. Is it a palindrome? Yes. Count = 3. This is our answer.

This is computationally expensive because the number of candidates to check can be enormous, especially for larger `intLength` values.

```java
class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] ans = new long[queries.length];
        long start = (long) Math.pow(10, intLength - 1);
        long end = (long) Math.pow(10, intLength);

        // This pre-computation is slightly better but still too slow for the given constraints
        java.util.List<Long> palindromes = new java.util.ArrayList<>();
        for (long num = start; num < end; num++) {
            if (isPalindrome(num)) {
                palindromes.add(num);
            }
        }

        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            if (query > 0 && query <= palindromes.size()) {
                ans[i] = palindromes.get(query - 1);
            } else {
                ans[i] = -1;
            }
        }
        return ans;
    }

    private boolean isPalindrome(long n) {
        String s = Long.toString(n);
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- For each `query` in the `queries` array:
  - Initialize a counter `count` to 0 and the result for this query to -1.
  - Determine the range of numbers to check: from `start = 10^(intLength - 1)` to `end = 10^intLength - 1`.
  - Iterate through each number `num` in this range.
  - For each `num`, check if it is a palindrome. This is typically done by converting the number to a string and checking if the string is identical to its reverse.
  - If `num` is a palindrome, increment `count`.
  - If `count` becomes equal to the current `query` value, we have found the desired palindrome. Store `num` as the result and break the inner loop.
  - If the loop finishes and the `query`-th palindrome hasn't been found, the result remains -1.
  - Add the result to the final answer array.

## Mathematical Construction
This efficient approach is based on a mathematical insight: any palindrome is uniquely determined by its first half. Instead of searching for palindromes, we can directly construct the k-th one. We calculate what the first half of the k-th palindrome must be, and then build the full palindrome from it.
**Time:** O(Q * L), where Q is the number of queries and L is `intLength`. For each query, we perform a constant number of arithmetic operations and string manipulations whose cost is proportional to the length of the number, L. · **Space:** O(Q + L), where Q is the number of queries and L is `intLength`. O(Q) is for the result array, and O(L) is temporary space for string manipulations per query.
**Pros:** Highly efficient with a time complexity linear in the number of queries.; Directly computes the answer without any searching or iteration over a large range of numbers.; Scales well with large `intLength` and large `query` values.
**Cons:** Requires careful handling of edge cases, such as odd vs. even `intLength`.; The numbers can exceed the capacity of a standard 32-bit integer, so `long` must be used.
### Explanation
The key observation is that a palindrome of length `L` is defined by its first `ceil(L/2)` digits. For instance, for `L=5`, the first 3 digits (e.g., `123`) determine the full palindrome (`12321`). For `L=4`, the first 2 digits (e.g., `45`) determine the palindrome (`4554`).

The k-th smallest palindrome of length `L` corresponds to the k-th smallest number that can form the first half. We can find this number directly.

1.  **Find the range of first halves:** The first half must be a number of length `halfLength = (intLength + 1) / 2`. The smallest such number is `10^(halfLength - 1)`. Let's call this `base`.
2.  **Find the k-th first half:** The 1st palindrome corresponds to `base`, the 2nd to `base + 1`, and so on. The `k`-th palindrome corresponds to the first half `base + k - 1`.
3.  **Construct the palindrome:** Once we have the first half, we construct the full palindrome. We take the string of the first half, and append the reverse of its prefix. If `intLength` is odd, we reverse the prefix excluding the last character. If `intLength` is even, we reverse the whole first half string.

This method avoids any iteration over non-palindromic numbers and calculates the result directly, making it highly efficient.

```java
class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] ans = new long[queries.length];
        int halfLength = (intLength + 1) / 2;
        long start = (long) Math.pow(10, halfLength - 1);
        long end = (long) Math.pow(10, halfLength);
        long totalPalindromes = end - start;

        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            if (query > totalPalindromes) {
                ans[i] = -1;
                continue;
            }
            
            // Calculate the first half of the palindrome
            long firstHalfNum = start + query - 1;
            String firstHalfStr = Long.toString(firstHalfNum);
            
            // Determine the part to be reversed for the second half
            String secondHalfPrefix;
            if (intLength % 2 == 1) {
                // For odd length, the middle character is not part of the reversed second half
                secondHalfPrefix = firstHalfStr.substring(0, firstHalfStr.length() - 1);
            } else {
                // For even length, the entire first half is reversed
                secondHalfPrefix = firstHalfStr;
            }
            
            // Reverse it to get the second half
            String secondHalfStr = new StringBuilder(secondHalfPrefix).reverse().toString();
            
            // Combine to form the full palindrome string and parse it
            String palindromeStr = firstHalfStr + secondHalfStr;
            ans[i] = Long.parseLong(palindromeStr);
        }
        return ans;
    }
}
```
### Algorithm
- Calculate the length of the first half of the palindrome: `halfLength = (intLength + 1) / 2`.
- Calculate the starting number for the first half. This is the smallest number of `halfLength` digits: `start = 10^(halfLength - 1)`.
- Calculate the total number of possible palindromes: `totalPalindromes = 9 * 10^(halfLength - 1)`.
- For each `query` in `queries`:
  - If `query` is greater than `totalPalindromes`, no such palindrome exists. The result is -1.
  - Otherwise, calculate the first half of the target palindrome: `firstHalfNum = start + query - 1`.
  - Convert `firstHalfNum` to its string representation, `firstHalfStr`.
  - Construct the second half of the palindrome by reversing a prefix of `firstHalfStr`. The prefix length is `intLength / 2`.
  - Concatenate `firstHalfStr` with the generated second half string.
  - Parse the resulting string into a `long` to get the final palindrome number.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  vector<long long> kthPalindrome(vector<int> &queries, int intLength) {
    int l = (intLength + 1) >> 1;
    long long start = pow(10, l - 1), end = pow(10, l) - 1;
    vector<long long> ans;
    for (int &q : queries) {
      long long v = start + q - 1;
      if (v > end) {
        ans.push_back(-1);
        continue;
      }
      string s = to_string(v);
      string s1 = s;
      reverse(s1.begin(), s1.end());
      s += s1.substr(intLength % 2);
      ans.push_back(stoll(s));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]: l = (intLength + 1) >> 1 start, end = 10 ** (l - 1), 10 ** l - 1 ans = [] for q in queries: v = start + q - 1 if v > end: ans . append(- 1) continue s = str(v) s += s[:: - 1][intLength % 2:] ans . append(int(s)) return ans

```