DEV Community

Cover image for SingleNumber
Amy Shackles
Amy Shackles

Posted on • Originally published at blog.amyshackles.com

SingleNumber

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
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

Problem taken from LeetCode

Top comments (0)