Kth digit of Nth Palindrome

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given two positive integers, 'N' and 'K'.

The sequence of positive palindromic numbers starts as 1, 2, 3, ..., 8, 9, 11, 22, 33, ..., 99, 101, 111, ... and so on.

Your task is to first find the N-th number in this sequence. Then, you must find the K-th digit of that number, reading from left to right.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

A single line containing two space-separated integers, 'N' and 'K'.

Output Format:

Print a single digit (0-9) which is the K-th digit of the N-th palindrome.
If 'K' is greater than the number of digits in the N-th palindrome, print -1.

Note:

The indexing for both 'N' and 'K' is 1-based.
The 1st palindrome is 1, the 9th is 9, the 10th is 11.

Sample Input 1:

10 1

Sample Output 1:

Explanation for Sample 1:

The first 9 palindromes are 1, 2, ..., 9.
The 10th palindrome in the sequence is 11.
The 1st digit (K=1) of 11 is 1.

Sample Input 2:

19 2

Sample Output 2:

Explanation for Sample 2:

The first 9 palindromes are single-digit.
The next 9 palindromes are two-digit (11, 22, ..., 99). This accounts for the 10th to 18th palindromes.
The 19th palindrome is the first one with three digits, which is 101.
The 2nd digit (K=2) of 101 is 0.

Expected Time Complexity:

The expected time complexity is O(log N)

Constraints:

1 <= N <= 10^12
1 <= K <= 18

Time limit: 1 sec

Approaches (1)

Approach 1

Kth digit of Nth Palindrome

The expected time complexity is O(log N)

Time Complexity

Space Complexity

(100% EXP penalty)

Kth digit of Nth Palindrome

Console