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 * 1041 <= queries[i] <= 1091 <= intLength <= 15
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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(''),
);
});
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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()
}
}
|
