Array
Math
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.
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
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 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 ( '' ),
);
});
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 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 ()
}
}
GitHub