AlgoDaily 08: Lonely Number

https://algodaily.com/challenges/lonely-number

“In a given array of numbers, one element will show up once and the rest will show up twice. Can you find that number in O(n) linear time?”

lonelyNumber([4, 4, 6, 1, 3, 1, 3])
// 6

lonelyNumber([3, 3, 9])
// 9

This seems straightforward.

function lonelyNumber(items) {
	return Object.keys(items.reduce((seen, x) => {
		if (x in seen) {
			delete seen[x];
			return seen;
		}
		seen[x] = x;
		return seen;
	}, {}))[0];
}

We start with an empty hash, then go through the array, removing an item we’ve seen before, and adding an item we haven’t.

This relies on the fact that there are guaranteed to be either one or two of any item.

Test cases:

lonelyNumber([4, 4, 6, 1, 3, 1, 3]);
// 6

lonelyNumber([3, 3, 9]);
// 9

lonelyNumber([1]);
// 1