My solution to a “Daily Coding Problem” that I received in my mail today.
You are given an array of length n + 1 whose elements belong to the set {1, 2, ..., n}. By the pigeonhole principle, there must be a duplicate. Find it in linear time and space.
Daily coding problem solution in Typescript,
oneSixtyFour(array: number[]): number | boolean{
//we know for sure the array will be length + 1
//no need to do null checks?
let uniqueVals = new Set<number>();
array.forEach(num => {
if(uniqueVals.has(num)) {
//we are assuming we return the first
//duplicate value we find
return num;
} else {
uniqueVals.add(num);
}
});
return false;
} How about an alternative?
oneSixtyFourSort(array: number[]): number | boolean{
//we know for sure the array will be length + 1
let uniqueVals = new Set<number>();
array.sort();
for(let i=1; i < array.length; i++ ){
if(array[i] == array[i-1]) {
return array[i];
}
}
return false;
}
Ok the second function is just an alternative solution, I reckon it’s slightly cleaner and better looking.
As usual, if you find any of my posts useful support me by buying or even trying one of my apps on the App Store.
Also, if you can leave a review on the App Store or Google Play Store, that would help too.
0 Comments