Skip to content

Instantly share code, notes, and snippets.

@erhanyasar
Last active July 26, 2023 20:19
Show Gist options
  • Save erhanyasar/53e2a0231dfb3249c7ce5ce1dc0dbb9f to your computer and use it in GitHub Desktop.
Save erhanyasar/53e2a0231dfb3249c7ce5ce1dc0dbb9f to your computer and use it in GitHub Desktop.
/*
Write a Function According to Given Brief:
The MEX number of a non-negative set of numbers is the smallest non-negative number that is not present in the set.
For example, MEX([1, 3, 10]) = 0, and MEX([0, 1, 2, 8]) = 3.
Your task is to take a given array arr of length num and remove the minimum number of elements from it so that,
the MEX value of the modified array is not equal to the MEX value of the original array.
- It should return the minimum number of elements that needed to be removed from the array
- If the task is not possible, then it should return -1.
Keep in mind:
- Arrray arr elements are non-negative integers,
- Array elements are not necessarily distinct,
- 1 <= num <= 40
- 0 <= arr[i] <= 90
Example:
For input parameters "num = 4" and "arr = [0, 1, 1, 4]" output should be "1".
Explanation:
The MEX of the input array is 2. If the element "0" at the index 0 would be removed, the
modified array [1, 1, 4] with MEX = 0 which is different than 2 exists. So the answer
would be "1" in that case meaning removing one element changed the MEX of the array.
*/
function min_removal(num, arr) {
let mex = -1,
sortedArr = [],
sortedSet = new Set(),
arrOfNumbers = [...Array(90).keys()];
removalsMap = new Map();
sortedArr = arr.sort((a, b) => a - b);
sortedArr.forEach((element) => sortedSet.add(element));
// First find mex
function findMex() {
Array.from(sortedSet).forEach((element, index) => {
if (element === arrOfNumbers[index]) {
if (mex === -1 && index === Array.from(sortedSet).length - 1)
mex = element + 1;
else return;
} else if (element > arrOfNumbers[index]) mex = arrOfNumbers[index];
});
return mex;
}
findMex();
// Then check min removal
function checkRemovals() {
let count;
const filteredSortedArr = sortedArr.filter((element) => element < mex);
filteredSortedArr.forEach((element, index) => {
let occurenceOfTheElement = filteredSortedArr.filter(
(el) => element === el
).length;
if (index === 0) count = occurenceOfTheElement;
removalsMap.set(element, occurenceOfTheElement);
if (count > occurenceOfTheElement) count = occurenceOfTheElement;
});
return count !== 0 ? count : -1;
}
return checkRemovals();
}
console.log(min_removal(5, [0, 0, 0, 1, 1, 1, 1]));
// with TypeScript --originally asked
export default function min_removal(num: Number, arr: number[]): number {
let mex: number = -1,
sortedArr: number[] = [],
sortedSet = new Set<number>(),
arrOfNumbers: number[] = [...Array(90).keys()],
removalsMap = new Map<number, number>();
sortedArr = arr.sort((a, b) => a - b);
sortedArr.forEach((element) => sortedSet.add(element));
// First find mex
function findMex() {
Array.from(sortedSet).forEach((element, index) => {
if (element === arrOfNumbers[index]) {
if (mex === -1 && index === Array.from(sortedSet).length - 1)
mex = element + 1;
else return;
} else if (element > arrOfNumbers[index]) mex = arrOfNumbers[index];
});
return mex;
}
findMex();
// Then check min removal
function checkRemovals() {
let count: number = 1;
const filteredSortedArr: number[] = sortedArr.filter(
(element) => element < mex
);
filteredSortedArr.forEach((element, index) => {
let occurenceOfTheElement: number = filteredSortedArr.filter(
(el) => element === el
).length;
if (index === 0) count = occurenceOfTheElement;
removalsMap.set(element, occurenceOfTheElement);
if (count > occurenceOfTheElement) count = occurenceOfTheElement;
});
return count !== 0 ? count : -1;
}
return checkRemovals();
}
console.log(min_removal(5, [0, 0, 0, 1, 1, 1, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment