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.


Tech mentioned