AlgoDaily 16: Missing Number In Unsorted
https://algodaily.com/challenges/missing-number-in-unsorted
The requirement to do this without sorting makes me think of using a hash map to
track each number we do see, and then finding the missing integer there by
iterating across the expected range. This isn’t O(n), though; it’s O(m+n).
function missingInUnsorted(numbers, lowerBound, upperBound) {
const seen = numbers.reduce((carry, num) => {
carry[num] = true;
return carry;
}, {});
for (let i = lowerBound; i < upperBound; i++) {
if (seen[i] === undefined) {
return i;
}
}
return undefined;
}
Algo Daily has a solution using the Gauss sum formula n(n+1)/2 to determine
the sum of a range of numbers, and then subtracting the sum of the given numbers
from that to find the single missing integer.
It seems like the same approach would also be possible without using the Gauss sum formula by simply summing the numbers between the lower bound and upper bound iteratively.