Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without extra memory?

Thought Process

My initial conclusion was that no, you couldn’t. Since there’s not a range for the possible numbers in the array and the array isn’t already sorted, you can solve in linear time if you used an object to store counts, but you need that extra storage or sorting is O(n log n).

But see, I forgot about XOR (^). For those of you who don’t play with bits, exclusive or takes two binary numbers and for pair where one number has the bit flipped and the other doesn’t, the resulting number has the bit flipped.

  01101
^ 10110
= 11011

So if you have a number and XOR it by 0, you get the number. If you have a number and XOR it by itself, you get 0.

Now, that’s helpful, but why would you care about XOR for this problem?

Let’s run through an example:

const input = [4,1,1,2,2,4,5,1,2,1,2]
let num = input[0];

for (let i = 1; i < input.length; i++) {
    num ^= input[i];
    console.log(num);
}

/*
5
4
6
4
0
5
4
6
7
5
*/

Explanation/Solution

Because all of the values that appear twice will eventually cancel themselves out, you’re left with that one solitary element that has no partner. No extra storage necessary. Linear time.

  100 // 4
^ 001 // 1
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 010 // 2
= 100 // 4
^ 100 // 4
= 000 // 0
^ 101 // 5
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 001 // 1
= 111 // 7
^ 010 // 2
= 101 // 5

Since we're working with an array of numbers, we can make use of an array method to accomplish the task in lieu of a for loop.

function singleNumber(nums) {
    return nums.reduce((a, b) => a ^ b)
}

Problem taken from LeetCode