# K-th smallest element after removing some integers from natural numbers

Given an array arr[] of size ‘n’ and a positive integer k. Consider series of natural numbers and remove arr, arr, arr, …, arr[p] from it. Now the task is to find k-th smallest number in the remaining set of natural numbers. If no such number exists print “-1”.

Examples :

```Input : arr[] = { 1 } and k = 1.
Output: 2
Natural numbers are {1, 2, 3, 4, .... }
After removing {1}, we get {2, 3, 4, ...}.
Now, K-th smallest element = 2.

Input : arr[] = {1, 3}, k = 4.
Output : 6
First 5 Natural number {1, 2, 3, 4, 5, 6,  .. }
After removing {1, 3}, we get {2, 4, 5, 6, ... }.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Simple):
Make an auxiliary array b[] for presence/absence of natural numbers and initialize all with 0. Make all the integer equal to 1 which are present in array arr[] i.e b[arr[i]] = 1. Now, run a loop and decrement k whenever unmarked cell is encountered. When the value of k is 0, we get the answer.

Below is implementation of this approach:

## C++

 `// C++ program to find the K-th smallest element ` `// after removing some integers from natural number. ` `#include ` `#define MAX 1000000 ` `using` `namespace` `std; ` ` `  `// Return the K-th smallest element. ` `int` `ksmallest(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// Making an array, and mark all number as unmarked. ` `    ``int` `b[MAX]; ` `    ``memset``(b, 0, ``sizeof` `b); ` ` `  `    ``// Marking the number present in the given array. ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``b[arr[i]] = 1; ` ` `  `    ``for` `(``int` `j=1; j

/div>

## Java

 `// Java program to find the K-th smallest element  ` `// after removing some integers from natural number. ` `class` `GFG ` `{ ` ` `  `    ``static` `final` `int` `MAX = ``1000000``; ` ` `  `    ``// Return the K-th smallest element.  ` `    ``static` `int` `ksmallest(``int` `arr[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``// Making an array, and mark  ` `        ``// all number as unmarked.  ` `        ``int` `b[] = ``new` `int``[MAX]; ` ` `  `        ``// Marking the number present ` `        ``// in the given array.  ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``{ ` `            ``b[arr[i]] = ``1``; ` `        ``} ` ` `  `        ``for` `(``int` `j = ``1``; j < MAX; j++) ` `        ``{ ` `            ``// If j is unmarked, reduce k by 1.  ` `            ``if` `(b[j] != ``1``) ` `            ``{ ` `                ``k--; ` `            ``} ` ` `  `            ``// If k is 0 return j.  ` `            ``if` `(k != ``1``) ` `            ``{ ` `                ``return` `j; ` `            ``} ` `        ``} ` `        ``return` `Integer.MAX_VALUE; ` `    ``} ` ` `  `    ``// Driven code  ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `k = ``1``; ` `        ``int` `arr[] = {``1``}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(ksmallest(arr, n, k)); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## Python3

 `# Python program to find the K-th smallest element ` `# after removing some integers from natural number. ` `MAX` `=` `1000000` ` `  ` `  `# Return the K-th smallest element. ` `def` `ksmallest(arr, n, k): ` `     `  `    ``# Making an array, and mark all number as unmarked. ` `    ``b ``=` `[``0``]``*``MAX``; ` ` `  `    ``# Marking the number present in the given array. ` `    ``for` `i ``in` `range``(n): ` `        ``b[arr[i]] ``=` `1``; ` ` `  `    ``for` `j ``in` `range``(``1``,``MAX``): ` `        ``# If j is unmarked, reduce k by 1. ` `        ``if` `(b[j] !``=` `1``): ` `            ``k``-``=``1``; ` ` `  `        ``# If k is 0 return j. ` `        ``if` `(k ``is` `not` `1``): ` `            ``return` `j; ` `             `  `# Driven Program ` `k ``=` `1``; ` `arr ``=` `[ ``1` `]; ` `n ``=` `len``(arr); ` `print``(ksmallest(arr, n, k)); ` ` `  `# This code contributed by Rajput-Ji `

## C#

 `// C# program to find the K-th smallest element  ` `// after removing some integers from natural number. ` `using` `System; ` ` `  `class` `GFG ` `{ ` ` `  `    ``static` `int` `MAX = 1000000; ` ` `  `    ``// Return the K-th smallest element.  ` `    ``static` `int` `ksmallest(``int` `[]arr, ``int` `n, ``int` `k) ` `    ``{ ` `        ``// Making an array, and mark  ` `        ``// all number as unmarked.  ` `        ``int` `[]b = ``new` `int``[MAX]; ` ` `  `        ``// Marking the number present ` `        ``// in the given array.  ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` `            ``b[arr[i]] = 1; ` `        ``} ` ` `  `        ``for` `(``int` `j = 1; j < MAX; j++) ` `        ``{ ` `            ``// If j is unmarked, reduce k by 1.  ` `            ``if` `(b[j] != 1) ` `            ``{ ` `                ``k--; ` `            ``} ` ` `  `            ``// If k is 0 return j.  ` `            ``if` `(k != 1) ` `            ``{ ` `                ``return` `j; ` `            ``} ` `        ``} ` `        ``return` `int``.MaxValue; ` `    ``} ` ` `  `    ``// Driven code  ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``int` `k = 1; ` `        ``int` `[]arr = {1}; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(ksmallest(arr, n, k)); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output :

```2
```

Time Complexity : O(n).

Method 2 (Efficient):
First, sort the array arr[]. Observe, there will be arr – 1 numbers between 0 and arr, similarly, arr – arr – 1 numbers between arr and arr and so on. So, if k lies between arr[i] – arr[i+1] – 1, then return K-th smallest element in the range. Else reduce k by arr[i] – arr[i+1] – 1 i.e., k = k – (arr[i] – arr[i+1] – 1).

Algorithm to solve the problem:

```1. Sort the array arr[].
2. For i = 1 to k. Find c = arr[i+1] - arr[i] -1.
a) if k - c <= 0, return arr[i-1] + k.
b) else k = k - c.
```
Below is implementation of this approach:

## C++

 `// C++ program to find the Kth smallest element ``// after removing some integer from first n ``// natural number. ``#include ``using` `namespace` `std; `` ` `// Return the K-th smallest element. ``int` `ksmallest(``int` `arr[], ``int` `n, ``int` `k) ``{ ``    ``sort(arr, arr+n); `` ` `    ``// Checking if k lies before 1st element ``    ``if` `(k < arr) ``        ``return` `k; `` ` `    ``// If k is the first element of array arr[]. ``    ``if` `(k == arr) ``        ``return` `arr + 1; `` ` `    ``// If k is more than last element ``    ``if` `(k > arr[n-1]) ``        ``return` `k + n; `` ` `    ``// If first element of array is 1. ``    ``if` `(arr == 1) ``        ``k--; `` ` `    ``// Reducing k by numbers before arr. ``    ``else``        ``k -= (arr - 1); `` ` `    ``// Finding k'th smallest element after removing ``    ``// array elements. ``    ``for` `(``int` `i=1; i

## Java

 `// Java program to find the  ` `// Kth smallest element after  ` `// removing some integer from  ` `// first n natural number. ` `import` `java.util.Arrays; ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `     `  `// Return the K-th ` `// smallest element. ` `static` `int` `ksmallest(``int` `arr[], ` `                     ``int` `n, ``int` `k) ` `{ ` `    ``// sort(arr, arr+n); ` `    ``Arrays.sort(arr); ` ` `  `    ``// Checking if k lies  ` `    ``// before 1st element ` `    ``if` `(k < arr[``0``]) ` `        ``return` `k; ` ` `  `    ``// If k is the first  ` `    ``// element of array arr[]. ` `    ``if` `(k == arr[``0``]) ` `        ``return` `arr[``0``] + ``1``; ` ` `  `    ``// If k is more ` `    ``// than last element ` `    ``if` `(k > arr[n - ``1``]) ` `        ``return` `k + n; ` ` `  `    ``// If first element  ` `    ``// of array is 1. ` `    ``if` `(arr[``0``] == ``1``) ` `        ``k--; ` ` `  `    ``// Reducing k by numbers ` `    ``// before arr. ` `    ``else` `        ``k -= (arr[``0``] - ``1``); ` ` `  `    ``// Finding k'th smallest  ` `    ``// element after removing ` `    ``// array elements. ` `    ``for` `(``int` `i = ``1``; i < n; i++) ` `    ``{ ` `        ``// Finding count of ` `        ``// element between i-th ` `        ``// and (i-1)-th element. ` `        ``int` `c = arr[i] - arr[i - ``1``] - ``1``; ` `        ``if` `(k <= c) ` `            ``return` `arr[i - ``1``] + k; ` `        ``else` `            ``k -= c; ` `    ``} ` ` `  `    ``return` `arr[n-``1``] + k; ` `} ` ` `  `// Driven Code ` `public` `static` `void` `main (String[] args)  ` `{ ` `    ``int` `k = ``1``; ` `    ``int` `arr[] = { ``1` `}; ` `    ``int` `n = arr.length; ` `    ``System.out.println(ksmallest(arr, n, k)); ` `} ` `} ` ` `  `// This code is contributed  ` `// by ajit `

## C#

 `// C# program to find the  ` `// Kth smallest element after  ` `// removing some integer from  ` `// first n natural number. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `// Return the K-th ` `// smallest element. ` `static` `int` `ksmallest(``int` `[]arr, ` `                     ``int` `n, ``int` `k) ` `{ ` `    ``// sort(arr, arr+n); ` `    ``Array.Sort(arr); ` ` `  `    ``// Checking if k lies  ` `    ``// before 1st element ` `    ``if` `(k < arr) ` `        ``return` `k; ` ` `  `    ``// If k is the first  ` `    ``// element of array arr[]. ` `    ``if` `(k == arr) ` `        ``return` `arr + 1; ` ` `  `    ``// If k is more ` `    ``// than last element ` `    ``if` `(k > arr[n - 1]) ` `        ``return` `k + n; ` ` `  `    ``// If first element  ` `    ``// of array is 1. ` `    ``if` `(arr == 1) ` `        ``k--; ` ` `  `    ``// Reducing k by numbers ` `    ``// before arr. ` `    ``else` `        ``k -= (arr - 1); ` ` `  `    ``// Finding k'th smallest  ` `    ``// element after removing ` `    ``// array elements. ` `    ``for` `(``int` `i = 1; i < n; i++) ` `    ``{ ` `        ``// Finding count of ` `        ``// element between i-th ` `        ``// and (i-1)-th element. ` `        ``int` `c = arr[i] -  ` `                ``arr[i - 1] - 1; ` `        ``if` `(k <= c) ` `            ``return` `arr[i - 1] + k; ` `        ``else` `            ``k -= c; ` `    ``} ` ` `  `    ``return` `arr[n-1] + k; ` `} ` ` `  `// Driver Code ` `static` `public` `void` `Main () ` `{ ` `    ``int` `k = 1; ` `    ``int` `[]arr = { 1 }; ` `    ``int` `n = arr.Length; ` `    ``Console.WriteLine(ksmallest(arr, n, k)); ` `} ` `} ` ` `  `// This code is contributed  ` `// by ajit `

## PHP

 ` ``\$arr``[``\$n` `- 1]) ` `        ``return` `\$k` `+ ``\$n``; ` ` `  `    ``// If first element  ` `    ``// of array is 1. ` `    ``if` `(``\$arr`` == 1) ` `        ``\$k``--; ` ` `  `    ``// Reducing k by numbers ` `    ``// before arr. ` `    ``else` `        ``\$k` `-= (``\$arr`` - 1); ` ` `  `    ``// Finding k'th smallest element  ` `    ``// after removing array elements. ` `    ``for` `(``\$i` `= 1; ``\$i` `< ``\$n``; ``\$i``++) ` `    ``{ ` `        ``// Finding count of element between  ` `        ``// i-th and (i-1)-th element. ` `        ``\$c` `= ``\$arr``[``\$i``] - ``\$arr``[``\$i` `- 1] - 1; ` `        ``if` `(``\$k` `<= ``\$c``) ` `            ``return` `\$arr``[``\$i` `- 1] + ``\$k``; ` `        ``else` `            ``\$k` `-= ``\$c``; ` `    ``} ` ` `  `    ``return` `\$arr``[``\$n` `- 1] + ``\$k``; ` `} ` ` `  `// Driver Code ` `\$k` `= 1; ` `\$arr` `= ``array` `( 1 ); ` `\$n` `= sizeof(``\$arr``); ` `echo` `ksmallest(``\$arr``, ``\$n``, ``\$k``); ` ` `  `// This code is contributed by aj_36 ` `?> `

Output :

```2
```

More efficient method : K-th smallest element after removing given integers from natural numbers | Set 2

Sorting Sorting