Find the Number

 Coding Problem Keys 

 Find the Number 

 Problem Statement 

You are given a string S of length N. The string S consists of digits from 1-9. Consider the string indexing to be 1-based.

You need to divide the string into blocks such that the i-th block contains the elements from the index((i - 1)* X + 1) to min (N, (i * X)) (both inclusive). A number is valid if it is formed by choosing exactly one digit from each block and placing the digits in the order of their block number.

 Example 

If the given string is '123456789' and X = 3, the blocks formed are [123], [456], [789]. A few valid numbers are 147, 159, 348, etc. but 124 and 396 are invalid.

Among all the valid numbers that can be formed, your task is to determine the Kth number if all the unique valid numbers are sorted in ascending order.

 Input Format 

First line: Three space-separated integers N, X, and K.

Second line: String S consisting of digits (1-9).

 Output Format 

Print the Kth valid number.

 Constraints 

1 ≤ N, X ≤ 10⁵

1 ≤ K ≤ 10¹⁸

 Example Input/Output 1 

 Input 

10 5 10

1234567891

 Output 

29

 Explanation 

The string can be divided into 2 blocks as follows:

[12345] and [67891].

The 10 th largest possible number is 29.

 Time Limit:  1.0 sec(s) for each input file
 Memory Limit:  256 MB
 Source Limit:  1024 KB

 Solution 

 Programming Language: Python 3 Language 

def Find_Number(N, X, K, S):
    S=list(S)
    blocks = [S[i:i + X] for i in range(0, N, X)]
    digits = [sorted(set(i)) for i in blocks]
    freq=[len(X) for X in digits]
    for i in range(len(freq)-2,-1,-1):
        freq[i]=freq[i]*freq[i+1]
    if K > freq[0]:
        return -1
    freq.append(1)
    ans = []
    K = K - 1
    for i in range(1, len(freq)):
        div = K // freq[i]
        ans.append(digits[i-1][div])
        K = K % freq[i]
    return (''.join(ans))
N, X, K = map(int, input().split())
S = input()
result=Find_Number(N, X, K, S)
print(result)

# Published By PKJCODERS
# Time - 0.800000 sec
# Memory - 58732 KiB

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.)