Here is the interview question prompt, presented for reference.
In a given array of numbers, one element will show up once and the others will each show up twice. Can you find the number that only appears once in
O(n) linear time? Bonus points if you can do it in
O(1) space as well.
```js lonelyNumber([4, 4, 6, 1, 3, 1, 3]) // 6
lonelyNumber([3, 3, 9]) // 9 ```
You can see the full challenge with visuals at this link.
Challenges • Asked over 1 year ago by Anonymous
This is the main discussion thread generated for Lonely Number.
Using delete on an object does not appear to work as intended. Running with an odd number of multiple appearances, like
console.log(lonelyNumber([4, 4, 6, 1, 1, 3, 1, 3])); returns
1 instead of the expected
6. I could not reduce the problem beyond setting to true or false if more than one, and then finding the first key with value of true. There is no built in method for this and it is potentially slow (?).
Your example has
1 appearing 3 times, so the 3rd time, it gets added back to the array.
I've added a note: "Note that this only works if the rest of the numbers show up an even number of times. This is because if a number shows up three or more times, you'll end up adding it back to the
What about using the count function? Isn't it still 0(n)?
for item in arr:
if arr.count(item) == 1:
This was the most helpful explanation of XOR I've read, still not sure I'd pull this out in an interview but it makes this bitwise operations seem much more accessible! Thanks!
So happy to hear that, Jacob :-) Check out https://algodaily.com/lessons/bitwise-operators-and-bit-manipulation-for-interviews for even more fun with bit manipulation!