Given an array arr[] of size ‘n’ and a positive integer k. Consider series of natural numbers and remove arr[0], arr[1], arr[2], …, arr[n-1] from it. Now the task is to find k-th smallest number in the remaining set of natural numbers.
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, … }.
Two methods are discussed in this article. This post discusses one more method.
Algorithm:
- Start traversing the array, for i ranging from 0 to N-1
- If arr[I] <= k, then increment k. Else break out of traversing the rest of the array
- The obtained k is the final answer
Note: This algorithm will only work if the input array is sorted. So first sort the given array (if not already) and in this case, the time complexity will become O(N log(N)).
Implementation:
C++
// C++ program to find the K-th smallest element// after removing some integers from natural number.#include <bits/stdc++.h>using namespace std;// Return the K-th smallest element.int ksmallest(int arr[], int n, int k){ for (int i = 0; i < n; i++) { if (arr[i] <= k) k++; else break; } return k;}// Driven Programint main(){ int k = 1; int arr[] = { 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << ksmallest(arr, n, k); return 0;} |
Java
// Java program to find the// K-th smallest element// after removing some // integers from natural number.class GFG{// Return the K-th // smallest element.static int ksmallest(int arr[], int n, int k){ for (int i = 0; i < n; i++) { if (arr[i] <= k) k++; else break; } return k;}// Driver Codepublic 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 Arnab Kundu |
Python3
# Python3 program to find # the K-th smallest element # after removing some integers# from natural number.# Return the K-th # smallest element.def ksmallest(arr, n, k): for i in range(n): if (arr[i] <= k): k = k + 1; else: break; return k;# Driver Codek = 1;arr = [1];n = len(arr);print(ksmallest(arr, n, k)); # This code is contributed by mits |
C#
// C# program to find the// K-th smallest element// after removing some // integers from natural number.using System;class GFG{// Return the K-th // smallest element.static int ksmallest(int []arr, int n, int k){ for (int i = 0; i < n; i++) { if (arr[i] <= k) k++; else break; } return k;}// Driver Codestatic public void Main (){ int k = 1; int []arr = { 1 }; int n = arr.Length; Console.WriteLine(ksmallest(arr, n, k));}}// This code is contributed @ajit |
Javascript
<script> // Javascript program to find the // K-th smallest element // after removing some // integers from natural number. // Return the K-th // smallest element. function ksmallest(arr, n, k) { for (let i = 0; i < n; i++) { if (arr[i] <= k) k++; else break; } return k; } let k = 1; let arr = [ 1 ]; let n = arr.length; document.write(ksmallest(arr, n, k));// This code is contributed by suresh07.</script> |
PHP
<?php// PHP program to find the K-th// smallest element after removing// some integers from natural number.// Return the K-th smallest element.function ksmallest($arr, $n, $k){ for ($i = 0; $i < $n; $i++) { if ($arr[$i] <= $k) $k++; else break; } return $k;} // Driver Code $k = 1; $arr = array(1); $n = sizeof($arr); echo ksmallest($arr, $n, $k); // This code is contributed by aj_36?> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
