Formatted question description: https://leetcode.ca/all/2217.html
2217. Find Palindrome With Fixed Length (Medium)
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
Companies:
VMware
Similar Questions:
Solution 1.
Let half
be the first half of the palindrome. The range of it is begin = 10^((len-1)/2)
(inclusive) to end = 10^((len+1)/2)
(exclusive).
For a given rank = Q[i]
, half = begin + Q[i] - 1
. We can use getPalindrome
helper function to generate the palindrome.
// OJ: https://leetcode.com/problems/find-palindrome-with-fixed-length/
// Time: O(QL)
// Space: O(1) extra space
class Solution {
long getPalindrome(long half, bool odd) {
long pal = half;
if (odd) half /= 10;
for (; half; half /= 10) pal = pal * 10 + half % 10;
return pal;
}
public:
vector<long long> kthPalindrome(vector<int>& Q, int len) {
long begin = pow(10L, (len - 1) / 2), end = pow(10L, (len + 1) / 2);
vector<long long> ans(Q.size(), -1);
for (int i = 0; i < Q.size(); ++i) {
long half = begin + Q[i] - 1;
if (half < end) ans[i] = getPalindrome(half, len % 2);
}
return ans;
}
};
Discuss
https://leetcode.com/problems/find-palindrome-with-fixed-length/discuss/1887018/