Welcome to Subscribe On Youtube

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

Related Topics:
Array, Math

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;
    }
};

  • 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 ans

############

# 2217. Find Palindrome With Fixed Length
# https://leetcode.com/problems/find-palindrome-with-fixed-length/

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        A = []
        inter = 2 if intLength % 2 == 0 else 1
        outer = (intLength - inter) // 2
        A = []
        
        if intLength <= 4:
            for x in range(10 ** (intLength - 1), 10 ** (intLength)):
                if str(x) == str(x)[::-1]:
                    A.append(str(x))
        
        def solve(x):
            if intLength <= 4:
                if x >= len(A): return -1
                return A[x]
            
            outIndex = x // 10
            out = 10 ** (outer - 1) + outIndex
            
            modIndex = x % 10
            
            res = str(out) + str(modIndex) * inter + str(out)[::-1]

            if len(res) != intLength: return -1
            
            return res

        res = []
        for q in queries:
            q -= 1
            res.append(solve(q))
        
        return res


  • 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;
    }
}

  • func kthPalindrome(queries []int, intLength int) []int64 {
	l := (intLength + 1) >> 1
	start, end := int(math.Pow10(l-1)), int(math.Pow10(l))-1
	var ans []int64
	for _, q := range queries {
		v := start + q - 1
		if v > end {
			ans = append(ans, -1)
			continue
		}
		t := v
		if intLength%2 == 1 {
			t /= 10
		}
		for t > 0 {
			v = v*10 + t%10
			t /= 10
		}
		ans = append(ans, int64(v))
	}
	return ans
}

  • function kthPalindrome(queries: number[], intLength: number): number[] {
    const isOdd = intLength % 2 === 1;
    const bestNum = 10 ** ((intLength >> 1) + (isOdd ? 1 : 0) - 1);
    const max = bestNum * 9;
    return queries.map(v => {
        if (v > max) {
            return -1;
        }
        const num = bestNum + v - 1;
        return Number(
            num +
                (num + '')
                    .split('')
                    .reverse()
                    .slice(isOdd ? 1 : 0)
                    .join(''),
        );
    });
}


  • impl Solution {
    pub fn kth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
        let is_odd = int_length & 1 == 1;
        let best_num = i32::pow(10, (int_length / 2 + if is_odd { 0 } else { -1 }) as u32);
        let max = best_num * 9;
        queries
            .iter()
            .map(|&num| {
                if num > max {
                    return -1;
                }
                let num = best_num + num - 1;
                format!(
                    "{}{}",
                    num,
                    num.to_string()
                        .chars()
                        .rev()
                        .skip(if is_odd { 1 } else { 0 })
                        .collect::<String>()
                )
                .parse()
                .unwrap()
            })
            .collect()
    }
}

Discuss

https://leetcode.com/problems/find-palindrome-with-fixed-length/discuss/1887018/

All Problems

All Solutions