Flag and Counting Approach
In this approach, Create an array flag of size MAX and initialize all elements to 0. Iterate through the array arr. For each element array[i], set flag[array[i]] to 1 to mark its presence Iterate from 1 to MAX. For each value i, if flag[i] is not equal to 1 indicating that i is not present in the array arr, decrement k. If k becomes 0, return the current value of i as the k-th smallest number. If no k-th smallest element is found return 0.
Example: The example below shows how to find the K-th smallest element after removing some integers from natural numbers using the Flag and Counting Approach.
const MAX = 1000000;
function smallestNumber(arr, n, k) {
const flag = new Array(MAX).fill(0);
for (let i = 0; i < n; i++) {
flag[arr[i]] = 1;
}
for (let i = 1; i < MAX; i++) {
if (flag[i] !== 1) {
k--;
}
if (k === 0) {
return i;
}
}
return 0;
}
const k = 2;
const arr = [3, 5];
console.log(smallestNumber(arr, 2, k));
Output
2
Time Complexity: O(MAX)
Space Complexity: O(MAX)
K-th Smallest Element after Removing some Integers from Natural Numbers using JavaScript
Given an array of size “n” and a positive integer k our task is to find the K-th smallest element that remains after removing certain integers from the set of natural numbers using JavaScript.
Example:
Input: array = [3, 5]
k = 2
Output: 2
Explanation: The natural numbers are [1, 2, 3, 4, 5......] and after removing elements 3 and 5 from the natural numbers, the remaining numbers are [1, 2, 4....].
The 2nd smallest number from the remaining numbers is 2.
Below are the approaches to finding the K-th smallest element after removing some integers from natural numbers using JavaScript:
Table of Content
- Brute Force approach
- Using Quick Select
- Flag and Counting Approach
- Using Sets