Last Updated: 20 Nov, 2021
K-th Number
Hard
Asked in company
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.
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
Approaches
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'.
Approach: The first observation is that while comparing two numbers for lexicographical order, the rest of the digits don't matter if their first digit is different.
E.g., All numbers [1, 120, 16582, 100000, 18572896] or any other number starting with digit' 1' will always be smaller than number '2' in lexicographical order.
The above observation applies to all the positions of digits.
Rather than checking all numbers starting with the digit 'x', and then moving to digit x+1, we can optimize it by calculating the count of numbers in the range [1...N], starting with digit 'x'.
If the above method is applied for all digits [0, 9], we can find the first digit of our answer. Repeat this method for all positions in the same manner.
Algorithm:
- Make a function, say 'calcSteps'.
- Function takes three arguments, say 'N', 'num1' and 'num2'.
- Returns count of numbers starting with 'num1', before reaching a number starting with 'num2'.
- If 'N' is reached before a number with 'num2', return the count till 'N'.
- Implementation :-
- Initialize 'counter' with zero.
- While 'num1' is less than or equal to 'N'.
- Take the minimum value among N+1 and 'num2', say 'minVal' and add the difference between 'minVal' and 'num1' to 'counter'.
- Multiply 'num1' and 'num2' with 10, to process the next position.
- Return' counter'.
- Our main function has two arguments: 'N' and 'K'.
- Initialize 'ans' with 1 and decrement 'K' by 1.
- While K is non-zero.
- Calculate the count of numbers starting with 'ans' using 'calcSteps'.
- If the count is less than or equal to 'K'.
- Reduce 'K' by this count.
- Increment the digit, i.e., ans = ans + 1.
- Else.
- Digit is fixed for this position and jump to the next position, i.e., ans = ans * 10.
- Decrement 'K' by 1.
- Return 'ans'.