This is the main discussion thread generated for Lonely Number.

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."

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

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 s = new HashSet<>();

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;

}

I like the solution you suggested but I generally prefer more intuitive solutions that would be slightly easier for an observer to unpack.

This solution isn't quite O(n) time complexity because it uses a sort but it is O(1) space complexity. In terms of absolute time to run, it's pretty much exactly the same as your bitwise solution (sometimes slower, sometimes faster).

1. Order the list
2. Loop through the ordered list a. If a number if surrounded by two different ones, then return it b. Otherwise, go to the next number along

def lonelyNumber(nums):
    nums.sort()
    for i, num in enumerate(nums):
        if i == 0:
            if nums[1] != num:
                return num
        elif i == len(nums) - 1:
            if nums[i - 1] != num:
                return num
        else:
            if nums[i - 1] != num and nums[i + 1] != num:
                return num

My only issue with it is that it uses a lot of if statements which I generally try to avoid for readability purposes.