Given an integer array queries and a positive integer intLength, return an arrayanswerwhereanswer[i]is either thequeries[i]thsmallestpositive palindrome of lengthintLengthor-1if no such palindrome exists.
A palindrome is a number that reads the same backwards and forwards.
Palindromes cannot have leading zeros.
Input: queries =[1,2,3,4,5,90], intLength =3Output: [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 3is999.
Input: queries =[2,4,6], intLength =4Output: [1111,1331,1551]Explanation:
The first six palindromes of length 4 are:1001,1111,1221,1331,1441, and 1551.
A palindrome is determined by its first half; the rest is a mirror. For a given length, we can generate the k-th palindrome by constructing the first half and reflecting it. This avoids generating all palindromes and is efficient even for large queries.
classSolution {
publiclong[]kthPalindrome(int[] queries, int intLength) {
int n = queries.length, half = (intLength + 1) / 2;
long[] ans =newlong[n];
long start = (long)Math.pow(10, half - 1), end = (long)Math.pow(10, half) - 1;
for (int i = 0; i < n; i++) {
long first = start + queries[i]- 1;
if (first > end) {
ans[i]=-1;
continue;
}
String s = Long.toString(first);
StringBuilder rev =new StringBuilder(s.substring(0, intLength / 2)).reverse();
ans[i]= Long.parseLong(s + rev);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funkthPalindrome(queries: IntArray, intLength: Int): LongArray {
val half = (intLength + 1) / 2val start = Math.pow(10.0, (half - 1).toDouble()).toLong()
val end = Math.pow(10.0, half.toDouble()).toLong() - 1return queries.map { q ->val first = start + q - 1if (first > end) -1Lelse {
val s = first.toString()
val rev = s.substring(0, intLength / 2).reversed()
(s + rev).toLong()
}
}.toLongArray()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defkthPalindrome(self, queries: list[int], intLength: int) -> list[int]:
ans = []
half = (intLength +1) //2 start =10** (half -1)
end =10** half -1for q in queries:
first = start + q -1if first > end:
ans.append(-1)
continue s = str(first)
rev = s[:intLength //2][::-1]
ans.append(int(s + rev))
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfnkth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
let half = (int_length +1) /2;
let start =10_i64.pow((half -1) asu32);
let end =10_i64.pow(half asu32) -1;
queries.iter().map(|&q| {
let first = start + q asi64-1;
if first > end { -1 }
else {
let s = first.to_string();
let rev: String = s.chars().take((int_length /2) asusize).rev().collect();
(s +&rev).parse().unwrap()
}
}).collect()
}
}