Kth Smallest Natural Number After Removing Some Numbers

Moderate

0/80

Contributed by

4 upvotes

Asked in companies

Problem statement

You have a list of all-natural numbers and an ‘arr’. Your task is to find the Kth smallest natural number after removing all numbers in ‘arr’ from the list of all-natural numbers.

Note: ‘arr’ will be sorted in ascending order.

For example:

You are given, ‘arr’ = [1, 2, 4], ‘K’ = ‘5’, You have the natural numbers as [1, 2, 3, 4, 5, 6, 7 .. ], after removing all the integers in the array from natural numbers, we have, [3, 5, 6, 7, 8]. Here 8 is the 5th smallest number. Hence the answer is 8.

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

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’, representing the size of ‘arr’ and ‘K’ the integer given.

The second line of each test case contains ‘N’ space-separated integers, representing the elements of the array ‘arr’.

Output Format:

For each test case print a single integer representing the ‘K’ the smallest integer after removing the integers of the array ‘arr’.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^3
1 <= K <= 10^6
1 <= arr[i] <= 10^5

Time Limit: 1 sec.

Sample Input 1:

Sample Output 1:

8
9

Explanation:

For the first test case,‘arr’ = [1, 2, 4], ‘K’ = ‘5’, You have the natural numbers as [1, 2, 3, 4, 5, 6, 7 .. ], after removing all the integers in the array from natural numbers, we have, [3, 5, 6, 7, 8]. Here 8 is the 5th smallest number. Hence the answer is 8.

For the second test case,‘arr’ = [1, 2, 4, 5], ‘K’ = ‘5’, You have the natural numbers as [1, 2, 3, 4, 5, 6, 7 .. ], after removing all the integers in the array from natural numbers, we have, [3, 6, 7, 8, 9]. Here 9 is the 5th smallest number. Hence the answer is 9.

Sample Input 2:

Sample Output 2:

6
6

Hint 1

Hint 2

Iterate over the natural numbers till you find the answer.

Approaches (2)

Approach 1

Approach 2

Simple Approach

In this approach, we will make a utility array or set and mark all the numbers present in the array. Now we simply count from 1 till we find K unmarked numbers.

Algorithm:

Create an empty set ‘markedNums’.
Iterate num through arr
- Insert num in markedNums
Iterate i from 1 to infinity
- If i is not present is markedNums
  - Decrease k by 1
- If k is equal to 0
  - Return i
Return -1

Time Complexity

O(N + K), Where N and K are the size of the array and the given integer.

We are iterating from 1 to infinity till K doesn’t become 0, we only decrease K when I is not present in the set. Hence the total time complexity is O(N + K).

Space Complexity

O(N), Where N is the size of the array.

We are maintaining a set of N numbers hence the overall space complexity is O(N).

(100% EXP penalty)

Kth Smallest Natural Number After Removing Some Numbers

Console