Find Palindrome With Fixed Length
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This naive approach involves generating and checking numbers one by one. For each query, it iterates through all numbers of the specified length, tests each for the palindrome property, and keeps a count. When the count matches the query number, the corresponding palindrome is found.
Algorithm
- For each
queryin thequeriesarray:- Initialize a counter
countto 0 and the result for this query to -1. - Determine the range of numbers to check: from
start = 10^(intLength - 1)toend = 10^intLength - 1. - Iterate through each number
numin this range. - For each
num, check if it is a palindrome. This is typically done by converting the number to a string and checking if the string is identical to its reverse. - If
numis a palindrome, incrementcount. - If
countbecomes equal to the currentqueryvalue, we have found the desired palindrome. Storenumas the result and break the inner loop. - If the loop finishes and the
query-th palindrome hasn't been found, the result remains -1. - Add the result to the final answer array.
- Initialize a counter
Walkthrough
The brute-force method directly simulates the process of finding the k-th palindrome. It starts from the smallest positive number of intLength and iterates upwards. In each step, it checks if the current number is a palindrome. A counter is maintained to track how many palindromes have been found. When this counter reaches the value specified by a query, the current number is the answer for that query. This entire process is repeated for every single query in the input array.
For example, to find the 3rd palindrome of length 3:
- Start with 100. Is it a palindrome? No.
-
- Is it a palindrome? Yes. Count = 1.
- 102...110. No.
-
- Is it a palindrome? Yes. Count = 2.
- 112...120. No.
-
- Is it a palindrome? Yes. Count = 3. This is our answer.
This is computationally expensive because the number of candidates to check can be enormous, especially for larger intLength values.
class Solution { public long[] kthPalindrome(int[] queries, int intLength) { long[] ans = new long[queries.length]; long start = (long) Math.pow(10, intLength - 1); long end = (long) Math.pow(10, intLength); // This pre-computation is slightly better but still too slow for the given constraints java.util.List<Long> palindromes = new java.util.ArrayList<>(); for (long num = start; num < end; num++) { if (isPalindrome(num)) { palindromes.add(num); } } for (int i = 0; i < queries.length; i++) { int query = queries[i]; if (query > 0 && query <= palindromes.size()) { ans[i] = palindromes.get(query - 1); } else { ans[i] = -1; } } return ans; } private boolean isPalindrome(long n) { String s = Long.toString(n); int len = s.length(); for (int i = 0; i < len / 2; i++) { if (s.charAt(i) != s.charAt(len - 1 - i)) { return false; } } return true; }}Complexity
Time
O(10^L * L + Q), where L is `intLength` and Q is the number of queries. The term `10^L * L` comes from iterating through all numbers of length L and checking if they are palindromes. This is prohibitively slow for the given constraints.
Space
O(N + P), where N is the number of queries and P is the total number of palindromes of `intLength`. In the worst case (`intLength=15`), P can be up to `9 * 10^7`, leading to high memory usage.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires minimal mathematical insight.
Cons
Extremely inefficient and slow.
Will result in a 'Time Limit Exceeded' error on any reasonably large test case due to the nested loops and large search space.
Repeats the same palindrome generation work for each query.
This efficient approach is based on a mathematical insight: any palindrome is uniquely determined by its first half. Instead of searching for palindromes, we can directly construct the k-th one. We calculate what the first half of the k-th palindrome must be, and then build the full palindrome from it.
Algorithm
- Calculate the length of the first half of the palindrome:
halfLength = (intLength + 1) / 2. - Calculate the starting number for the first half. This is the smallest number of
halfLengthdigits:start = 10^(halfLength - 1). - Calculate the total number of possible palindromes:
totalPalindromes = 9 * 10^(halfLength - 1). - For each
queryinqueries:- If
queryis greater thantotalPalindromes, no such palindrome exists. The result is -1. - Otherwise, calculate the first half of the target palindrome:
firstHalfNum = start + query - 1. - Convert
firstHalfNumto its string representation,firstHalfStr. - Construct the second half of the palindrome by reversing a prefix of
firstHalfStr. The prefix length isintLength / 2. - Concatenate
firstHalfStrwith the generated second half string. - Parse the resulting string into a
longto get the final palindrome number.
- If
Walkthrough
The key observation is that a palindrome of length L is defined by its first ceil(L/2) digits. For instance, for L=5, the first 3 digits (e.g., 123) determine the full palindrome (12321). For L=4, the first 2 digits (e.g., 45) determine the palindrome (4554).
The k-th smallest palindrome of length L corresponds to the k-th smallest number that can form the first half. We can find this number directly.
- Find the range of first halves: The first half must be a number of length
halfLength = (intLength + 1) / 2. The smallest such number is10^(halfLength - 1). Let's call thisbase. - Find the k-th first half: The 1st palindrome corresponds to
base, the 2nd tobase + 1, and so on. Thek-th palindrome corresponds to the first halfbase + k - 1. - Construct the palindrome: Once we have the first half, we construct the full palindrome. We take the string of the first half, and append the reverse of its prefix. If
intLengthis odd, we reverse the prefix excluding the last character. IfintLengthis even, we reverse the whole first half string.
This method avoids any iteration over non-palindromic numbers and calculates the result directly, making it highly efficient.
class Solution { public long[] kthPalindrome(int[] queries, int intLength) { long[] ans = new long[queries.length]; int halfLength = (intLength + 1) / 2; long start = (long) Math.pow(10, halfLength - 1); long end = (long) Math.pow(10, halfLength); long totalPalindromes = end - start; for (int i = 0; i < queries.length; i++) { int query = queries[i]; if (query > totalPalindromes) { ans[i] = -1; continue; } // Calculate the first half of the palindrome long firstHalfNum = start + query - 1; String firstHalfStr = Long.toString(firstHalfNum); // Determine the part to be reversed for the second half String secondHalfPrefix; if (intLength % 2 == 1) { // For odd length, the middle character is not part of the reversed second half secondHalfPrefix = firstHalfStr.substring(0, firstHalfStr.length() - 1); } else { // For even length, the entire first half is reversed secondHalfPrefix = firstHalfStr; } // Reverse it to get the second half String secondHalfStr = new StringBuilder(secondHalfPrefix).reverse().toString(); // Combine to form the full palindrome string and parse it String palindromeStr = firstHalfStr + secondHalfStr; ans[i] = Long.parseLong(palindromeStr); } return ans; }}Complexity
Time
O(Q * L), where Q is the number of queries and L is `intLength`. For each query, we perform a constant number of arithmetic operations and string manipulations whose cost is proportional to the length of the number, L.
Space
O(Q + L), where Q is the number of queries and L is `intLength`. O(Q) is for the result array, and O(L) is temporary space for string manipulations per query.
Trade-offs
Pros
Highly efficient with a time complexity linear in the number of queries.
Directly computes the answer without any searching or iteration over a large range of numbers.
Scales well with large
intLengthand largequeryvalues.
Cons
Requires careful handling of edge cases, such as odd vs. even
intLength.The numbers can exceed the capacity of a standard 32-bit integer, so
longmust be used.
Solutions
Solution
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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.