Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2217.html

2217. Find Palindrome With Fixed Length (Medium)

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

Companies:
VMware

Related Topics:
Array, Math

Similar Questions:

• Palindrome Number (Easy)
• Find the Closest Palindrome (Hard)

Solution 1.

Let half be the first half of the palindrome. The range of it is begin = 10^((len-1)/2) (inclusive) to end = 10^((len+1)/2) (exclusive).

For a given rank = Q[i], half = begin + Q[i] - 1. We can use getPalindrome helper function to generate the palindrome.

• C++
• Java
• Python

• // OJ: https://leetcode.com/problems/find-palindrome-with-fixed-length/
  // Time: O(QL)
  // Space: O(1) extra space
  class Solution {
      long getPalindrome(long half, bool odd) {
          long pal = half;
          if (odd) half /= 10;
          for (; half; half /= 10) pal = pal * 10 + half % 10;
          return pal;
      }
  public:
      vector<long long> kthPalindrome(vector<int>& Q, int len) {
          long begin = pow(10L, (len - 1) / 2), end = pow(10L, (len + 1) / 2);
          vector<long long> ans(Q.size(), -1);
          for (int i = 0; i < Q.size(); ++i) {
              long half = begin + Q[i] - 1;
              if (half < end) ans[i] = getPalindrome(half, len % 2);
          }
          return ans;
      }
  };
  

• // Todo
  

• 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
  
  ############
  
  # 2217. Find Palindrome With Fixed Length
  # https://leetcode.com/problems/find-palindrome-with-fixed-length/
  
  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
  
  

Discuss

https://leetcode.com/problems/find-palindrome-with-fixed-length/discuss/1887018/

All Problems

All Solutions