We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Palindrome With Fixed Length

Number: 1375

Difficulty: Medium

Paid? No

Companies: TikTok, VMware

Problem Description

Given an integer array queries and a positive integer intLength, find the queries[i]th smallest positive palindrome of length intLength for each query. If the query is greater than the number of palindromes of that fixed length, return -1 for that query. A palindrome reads the same backwards and forwards, and palindromic numbers must not have leading zeros.

Key Insights

  • The palindrome can be constructed from a prefix (first half of the number). For an odd intLength, the middle digit is shared.
  • The number of valid palindromes is determined by the range of valid first-half numbers. The starting prefix is 10^(half-1) (to avoid leading zeros) and the count is 9 * 10^(half-1).
  • For each query, if the query index exceeds the count of available prefixes, return -1.
  • Convert the prefix into a palindrome by mirroring it appropriately depending on whether the intLength is even or odd.

Space and Time Complexity

Time Complexity: O(q * p) where q is the number of queries and p is the number of digits in the prefix (at most 8 given constraints), which is efficient for q up to 5 * 10^4. Space Complexity: O(q) to store the resulting palindrome for each query.

Solution

The solution involves generating palindromic numbers using the following steps:

  1. Determine half the length needed to build the palindrome. If intLength is odd, let half = (intLength + 1) // 2; otherwise, half = intLength // 2.
  2. Compute the starting prefix as start = 10^(half - 1) and the maximum number of prefixes as count = 9 * 10^(half - 1).
  3. For each query, check if the query's value is more than count. If so, return -1.
  4. Otherwise, calculate the prefix number by adding (query - 1) to the starting prefix.
  5. Convert the prefix to a string to build the final palindrome:
    • For even intLength: Concatenate prefix string with its reverse.
    • For odd intLength: Concatenate prefix string with the reverse of the prefix string excluding the last character.
  6. Append the computed palindrome (as an integer) to the answer list.

The main trick is realizing that the queries correspond directly to the order of the first-half prefixes.

Code Solutions

# Python solution to construct the kth smallest palindrome of a given fixed length.
class Solution:
    def kthPalindrome(self, queries, intLength):
        # Calculate half length which determines the prefix.
        half = (intLength + 1) // 2
        # start is the smallest number with half digits (ensuring no leading zeros)
        start = 10 ** (half - 1)
        # The total number of palindromic numbers that can be formed
        total_count = 9 * (10 ** (half - 1))
        
        result = []
        for k in queries:
            # If kth query exceeds the number of possible prefixes, append -1.
            if k > total_count:
                result.append(-1)
                continue
            # Calculate the actual prefix based on k.
            prefix_num = start + k - 1
            prefix_str = str(prefix_num)
            # Build the palindrome by reflecting the prefix.
            if intLength % 2 == 0:
                # Even length: mirror the entire prefix.
                palindrome = prefix_str + prefix_str[::-1]
            else:
                # Odd length: mirror omitting the last digit of the prefix.
                palindrome = prefix_str + prefix_str[-2::-1]
            result.append(int(palindrome))
        return result

# Example usage:
# sol = Solution()
# print(sol.kthPalindrome([1,2,3,4,5,90], 3)) # Expected Output: [101,111,121,131,141,999]
← Back to All Questions