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.

Here’s my 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.

Like the blog? Subscribe for updates

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. 

https://mydaytodo.com/apps/

Also, if you can leave a review on the App Store or Google Play Store, that would help too.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *