K-th Number

Hard
0/120
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in company
Bytedance

Problem statement

You are given a positive integer 'N'. Generate an array 'A' having all integers in range [1, N] exactly once, i.e., array 'A' will be [1, 2, 3, ….., N-1, N]. Your task is to sort array 'A' in lexicographical order.

E.g. If N = 12, array ‘A’ will be [1, 2, 3, ….. 11, 12]. After lexicographical sorting, array ‘A’ becomes [1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9].

Sort array 'A' into lexicographical order and print the number appearing at K-th position.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains 'T', denoting the number of tests.
For each Test :
    The only line contains two space-separated integers 'N' and 'K'.
Output Format: 
For each test, print one integer, denoting the number appearing at K-th position when the array 'A' is sorted in lexicographical order.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= 'T' <= 10^3
1 <= 'K' <= 'N' <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
13 2
5 5
Sample Output 1 :
10
5
Explanation for Sample Input 1 :
For case 1:
    For N = 13, array 'A' is [1, 2, 3, 4, ….., 12, 13]. After lexicographical sorting, array 'A' becomes [1, 10, 11, 12, 13, 2, 3, …. 8, 9] which has number 10 at its second position.

For Case 2:
    Before and After sorting, array 'A' remains the same which is [1, 2, 3, 4, 5]. Number 5 appears at 5th position.
Sample Input 2 :
2
25 10
17 11
Sample Output 2 :
18
3
Hint

Do sorting integers and strings are the same?

Approaches (2)
Brute Force

Approach: Generated array 'A' has all the integers in the range [1….N]. To sort them lexicographically, convert each integer into a string. Applying the sort function on an array of strings will sort the array in lexicographical order. Now, select the string at K-th position, convert it back into an integer, and return it.

 

Algorithm:

  • Create an empty vector 'vec' of strings.
  • Iterate a for loop i = 1 to N.
    • After converting integer 'i' into string format, insert it into the vector 'vec'.
  • Apply sort function on vector' vec'.
  • Let the string at K-th position is 'num' (K-1'th element will be selected because of 0-based indexing).
  • Return integer form of 'num'.
Time Complexity

O(N logN), where 'N' is provided in input data and denotes the range of array elements.

Sorting an array of 'N' elements has time complexity O(N logN). Hence overall time complexity becomes O(N logN).

Space Complexity

O(N), where 'N' is provided in input data and denotes the range of array elements.

An array of size 'N' is created. Hence overall space complexity becomes O(N).

Code Solution
(100% EXP penalty)
K-th Number
Full screen
Console