Skip to content

2217. Find Palindrome With Fixed Length

Difficulty Topics

Description

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

Solution

find-palindrome-with-fixed-length.py
class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        A = []
        inter = 2 if intLength % 2 == 0 else 1
        outer = (intLength - inter) // 2
        A = []

        if intLength <= 4:
            for x in range(10 ** (intLength - 1), 10 ** (intLength)):
                if str(x) == str(x)[::-1]:
                    A.append(str(x))

        def solve(x):
            if intLength <= 4:
                if x >= len(A): return -1
                return A[x]

            outIndex = x // 10
            out = 10 ** (outer - 1) + outIndex

            modIndex = x % 10

            res = str(out) + str(modIndex) * inter + str(out)[::-1]

            if len(res) != intLength: return -1

            return res

        res = []
        for q in queries:
            q -= 1
            res.append(solve(q))

        return res