Find Palindrome With Fixed Length

'''
    Rules:
    1. A palindrome is fully determined by its first half.
       - Even n → first half length = n // 2
       - Odd n  → first half length = n // 2 + 1
    2. The smallest valid first half (no leading zeros):
       - Even n → start = 10**(n//2 - 1)
       - Odd n  → start = 10**(n//2)
    3. Compute the k-th first half:
       first_half = start + (k - 1)
    4. Form the palindrome by mirroring:
       - Even n → palindrome = first_half + reversed(first_half)
       - Odd n  → palindrome = first_half + reversed(first_half)[1:]
    5. If the resulting palindrome length != n, return -1.
    6. Use str() and [::-1] for string reversal, int() for final number.
'''

class Solution:
    def kthPalindrome(self, q: List[int], n: int) -> List[int]:
        ans = []

        if n % 2:
            start = pow(10, n // 2)
        else:
            start = pow(10, (n // 2) - 1)

        for i in range(len(q)):
            first = str(start + q[i] - 1)
            second = first[::-1]

            if n % 2:
                val = first + second[1:]
                if len(val) != n:
                    ans.append(-1)
                else:
                    ans.append(int(val))     # inbuilt conversion
            else:
                val = first + second
                if len(val) != n:
                    ans.append(-1)
                else:
                    ans.append(int(val))     # inbuilt conversion

        return ans