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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Palindrome With Fixed Length

Difficulty: Medium

Problem 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.

Key Insights

  • Palindromes can be generated by mirroring half of the number.
  • The first half of a number determines the palindrome uniquely.
  • For odd intLength, the middle digit can be any digit from 0 to 9.
  • For even intLength, the number is a direct mirror of the first half.
  • The range of valid numbers depends on the intLength, which can be derived from the number of digits.

Space and Time Complexity

Time Complexity: O(n), where n is the number of queries since we can compute the palindromes directly based on the queries. Space Complexity: O(n), for storing the results of the queries.

Solution

To solve this problem, we can generate palindromes by constructing them from their first half. First, we determine the starting and ending numbers based on the intLength. For each query, we compute the palindrome using the first half of the number and mirror it to create the full palindrome.

Code Solutions

def kthPalindrome(queries, intLength):
    answer = []
    start = 10 ** ((intLength - 1) // 2)  # starting point for half
    end = 10 ** ((intLength + 1) // 2)    # end point for half

    for q in queries:
        half_number = start + q - 1
        if half_number >= end:
            answer.append(-1)
        else:
            half_str = str(half_number)
            if intLength % 2 == 0:  # even length
                palindrome = half_str + half_str[::-1]
            else:  # odd length
                palindrome = half_str + half_str[-2::-1]
            answer.append(int(palindrome))
    
    return answer
← Back to All Questions