Problem
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 * 10^41 <= queries[i] <= 10^91 <= intLength <= 15
Solution (Java)
class Solution {
public long[] kthPalindrome(int[] queries, int intLength) {
long minHalf = (long) Math.pow(10, (intLength - 1) / 2);
long maxIndex = (long) Math.pow(10, (intLength + 1) / 2) - minHalf;
boolean isOdd = intLength % 2 == 1;
long[] res = new long[queries.length];
for (int i = 0; i < res.length; i++) {
res[i] = queries[i] > maxIndex ? -1 : helper(queries[i], minHalf, isOdd);
}
return res;
}
private long helper(long index, long minHalf, boolean isOdd) {
long half = minHalf + index - 1;
long res = half;
if (isOdd) {
res /= 10;
}
while (half != 0) {
res = res * 10 + half % 10;
half /= 10;
}
return res;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).