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.

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

- Length of the array <=
`100000`

- The values of the array will be between
`-1000000000`

and`1000000000`

You can see the full challenge with visuals at this link.

**Challenges**
â€¢ Asked almost 2 years 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 (?).

Hi,

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 `hash map`

."

[deleted]

What about using the count function? Isn't it still 0(n)?

def lonely_number2(arr):

for item in arr:

if arr.count(item) == 1:

return item

[deleted]

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!

How about using Math to solve the problem:-

Idea -> 2 * (a + b + c) - (a + a + b + b + c) = c

Code:

public int lonelyNumber(int[] nums) {

int sumOfNums = 0, sumOfSet = 0;

Set

for(int x : nums) {

if (!s.contains(x)) {

s.add(x);

sumOfSet += x; // set will contain only unique elements from given array

}

sumOfNums += x;

}

return 2 * sumOfSet - sumOfNums;

}