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.

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

## Solution: Math

For even length e.g. 4, we work with length / 2, e.g. 2. Numbers: 10, 11, 12, …, 99, starting from 10, ends with 99, which consist of 99 – 10 + 1 = 90 numbers. For the x-th number, e.g. 88, the left part is 10 + 88 – 1 = 97, just mirror it o get the palindrome. 97|79. Thus we can answer a query in O(k/2) time which is critical.

For odd length e.g. 3 we work with length / 2 + 1, e.g. 2, Numbers: 10, 11, 12, 99. Drop the last digit and mirror the left part to get the palindrome. 101, 111, 121, …, 999.

Time complexity: O(n)
Space complexity: O(1)

## C++

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode