Question

2217. Find Palindrome With Fixed Length

中文文档

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

Solutions

Solution 1

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

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;
  }
}

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;
  }
};

func kthPalindrome(queries []int, intLength int) []int64 {
  l := (intLength + 1) >> 1
  start, end := int(math.Pow10(l-1)), int(math.Pow10(l))-1
  var ans []int64
  for _, q := range queries {
    v := start + q - 1
    if v > end {
      ans = append(ans, -1)
      continue
    }
    t := v
    if intLength%2 == 1 {
      t /= 10
    }
    for t > 0 {
      v = v*10 + t%10
      t /= 10
    }
    ans = append(ans, int64(v))
  }
  return ans
}

function kthPalindrome(queries: number[], intLength: number): number[] {
  const isOdd = intLength % 2 === 1;
  const bestNum = 10 ** ((intLength >> 1) + (isOdd ? 1 : 0) - 1);
  const max = bestNum * 9;
  return queries.map(v => {
    if (v > max) {
      return -1;
    }
    const num = bestNum + v - 1;
    return Number(
      num +
        (num + '')
          .split('')
          .reverse()
          .slice(isOdd ? 1 : 0)
          .join(''),
    );
  });
}

impl Solution {
  pub fn kth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
    let is_odd = (int_length & 1) == 1;
    let best_num = i32::pow(10, (int_length / 2 + (if is_odd { 0 } else { -1 })) as u32);
    let max = best_num * 9;
    queries
      .iter()
      .map(|&num| {
        if num > max {
          return -1;
        }
        let num = best_num + num - 1;
        format!(
          "{}{}",
          num,
          num
            .to_string()
            .chars()
            .rev()
            .skip(if is_odd { 1 } else { 0 })
            .collect::<String>()
        )
          .parse()
          .unwrap()
      })
      .collect()
  }
}