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
Brute Force approach
In this approach, Generate all the natural numbers up to a certain limit, then filter out the numbers that are not present in the given array. After filtering, sort the remaining numbers and return the K-th smallest one.
Example: The example below shows how to find the K-th smallest element after removing some integers from natural numbers using JavaScript.
function kthSmallestAfterRemoval(arr, k, MAX) {
const naturalNumbers =
Array.from({ length: MAX }, (_, i) => i + 1);
const remainingNumbers =
naturalNumbers.filter(num => !arr.includes(num));
remainingNumbers.sort((a, b) => a - b);
return remainingNumbers[k - 1];
}
const arr = [3, 5];
const k = 2;
const MAX = 10;
console.log("K-th smallest element after removal:",
kthSmallestAfterRemoval(arr, k, MAX));
Output
K-th smallest element after removal: 2
Time complexity: O(MAX + n log n)
Space complexity: O(MAX + n)
Using Quick Select
In this approach, Implement the Quick Select algorithm to find the K-th smallest element in an array. Modify the algorithm to handle the removal of integers that do not meet the specified condition. Use the modified Quick Select algorithm to find the K-th smallest integer after removing the specified integers from the natural numbers
Example: The example below shows how to find the K-th smallest element after removing some integers from natural numbers using Quick Select.
function partition(arr, left, right, pivotIndex) {
const pivotValue = arr[pivotIndex];
let storeIndex = left;
// Move pivot to the end
[arr[pivotIndex], arr[right]] =
[arr[right], arr[pivotIndex]];
// Partition the array
for (let i = left; i < right; i++) {
if (arr[i] < pivotValue) {
[arr[i], arr[storeIndex]] =
[arr[storeIndex], arr[i]];
storeIndex++;
}
}
// Move pivot to its final place
[arr[right], arr[storeIndex]] =
[arr[storeIndex], arr[right]];
return storeIndex;
}
function quickSelect(arr, left, right, k) {
while (left <= right) {
const pivotIndex = Math.floor(Math.random() *
(right - left + 1)) + left;
const partitionIndex =
partition(arr, left, right, pivotIndex);
if (partitionIndex === k) {
return arr[partitionIndex];
} else if (partitionIndex < k) {
left = partitionIndex + 1;
} else {
right = partitionIndex - 1;
}
}
}
function kthSmallestAfterRemoval(arr, k, MAX) {
const remainingNumbers = [];
let num = 1;
while (remainingNumbers.length < k) {
if (!arr.includes(num)) {
remainingNumbers.push(num);
}
num++;
}
return quickSelect(remainingNumbers, 0,
remainingNumbers.length - 1, k - 1);
}
const arr = [3, 5];
const k = 2;
const MAX = 10;
console.log("K-th smallest element after removal:",
kthSmallestAfterRemoval(arr, k, MAX));
Output
K-th smallest element after removal: 2
Time complexity: O(n)
Space complexity: O(k)
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)
Using Sets
In this approach, Initialize an empty set to store the integers in the array. Start a loop from 1 (the smallest natural number). Check if the current number exists in the set. If it doesn’t, increment the count of found smallest elements. Inside the loop, if the count of found smallest elements equals k, return the current number.
Example: The example below shows how to find K-th smallest element after removing some integers from natural numbers using Sets.
function kthSmallestAfterRemoval(array, k) {
// Create a Set to store integers in the array
const set = new Set(array);
// Count smallest elements
let count = 0;
for (let i = 1; ; i++) {
// increment the count
if (!set.has(i)) {
count++;
// Return the k-th smallest number
if (count === k) return i;
}
}
}
const array = [3, 5];
const k = 2;
console.log(kthSmallestAfterRemoval(array, k));
Output
2
Time Complexity: O(n + k).
Space Complexity: O(n)