Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

• 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
  
  

• 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()
      }
  }
  
  

All Problems

All Solutions