How to find a unique number in a list containing pairs?

Finding a single unique number in a list containing pairs might sound pretty simple, right?

Because a one-sentence description might be misleading, let’s start with an example of an input array:

[1,3,17,3,1]

Given such an array, the unique number is the one that appears only once (17). The rest of the numbers (1 and 3) will appear twice. For the sake of this exercise, we can assume this is always true.

Performance wise, there are 3 main ways to do that. O(n*n), O(n) time and O(n) space and, with a little bitwise trick, O(n) time and O(1) space. After reading this article, you’ll know all three.

The Naive Solution

Let’s find the unique number in [1,3,17,3,1]. Easy peasy:

function singleNumber(nums) {
for (let i = 0; i < nums.length; i++) {
let found = false;
for (let j = 0; j < nums.length; j++) {
if (nums[j] === nums[i] && i != j) {
found = true;
break;
}
}
if (!found) return nums[i];
}
};

This solution goes over all the numbers and verifies they are not duplicate. Worst case, we go over the list once for every member in the list. That means, O(n*n).

How to solve finding unique value in a list containing pairs in linear time?

When writing a solution to a problem, we’d usually like to solve it linearly. The solution would be to use a hash or a memo object to remember what numbers appeared more than once:

function findUniqueNumber(nums) {
let memo = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (!memo[num]) {
memo[num] = 1;
} else {
memo[num] += 1;
}
}
return Object.keys(memo).reduce((unique,num) => {
return memo[num] === 1 ? Number(num) : unique;
}, NaN);
};

The memo object on line 2 will be our memory of what numbers we saw more than once. Then we iterate over our nums array. If the number appears for the first time, we initialize a memory hash for this number with the value of 1. That means, it appeared once. If we stumble upon this number again, we raise the counter by 1 for this number.

In lines 11-13 we go over our hash table and extract the value that appeared only once.

This code works linearly (O(n)), because we don’t have a nested loop. On the other hand, we are now using the memo object which is using O(n/2) space (which is actually O(n)). Can we make it better?

How to Use Bitwise XOR to find a unique value in a list containing pairs in linear time?

I’ve written in the past about the merits of bitwise operators. Here’s a trick that I hope will help you remember the bitwise XOR (^) operator.

Bitwise XOR has two steps:

  1. Turn the numbers into a 32-bit signed binary number.
  2. Return a new number with the following rules: if both bits are 1 or 0, return 0. Otherwise – return 1.

Here’s an example: 4 ^ 5

4 in binary is 100 while 5 is 101. Turning them into 32 bits will just pad them in zeros to the left.

Eventually, we will need to XOR these two binary numbers: 100 and 101.

Going from left to write we have:

1 and 1 => 0

0 and 0 => 0

0 and 1 => 1

So the final result will be: 001 which is 1. You can try it in the console right now.

The trick is this – XORing the same number (e.g. 4 ^ 4) will always result in 0. So if we have an array containing pairs, doing the following will result in zero:

[1,2,3,4,5,6,7,1000000,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

If we had one unique number in the list… you see where it’s going? Try this in the console:

[1,2,3,4,5,6,7,1000000,8,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

Because similar pairs cancel each other, having one unique value will “stand out” when XORing all of the numbers. And for bitwise XOR the order of the elements doesn’t matter. If we have an odd amount of 1’s, the resulting bit will be 1. Otherwise it will be 0.

And now we have a one line linear time solution for our problem with an O(1) space complexity:

function findUniqueNumber(nums) {
return nums.reduce((val, num) => val ^ num);
}

Summary

Finding a unique value in a list containing pairs is a small problem that is mostly used in interviews. It’s not very interesting unto itself.

In this article, we saw two ways to solve it in linear time. I hope that it also tricked you to know what bitwise XOR is :). Note that this trick is good to separate odd and even. If we had more than pairs, this would not have worked…

If you want to know more ways of how Bitwise operations can be good for performance, I’ve written about it here and here.

Thanks a lot to Tal Weinfeld for the kind review.

Sign up to my newsletter to enjoy more content:

0 0 votes
Article Rating
Subscribe
Notify of
guest

3 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
David
David
2 years ago

What do you mean by “list of pairs”?

You start with the example: [1,3,17,3,1]

I would have expected a list of pairs such as: ((1 3) (17 3) (1 137))

That is, a list containing pairs (an even number of elements).

zhu
zhu
2 years ago

I get another functions to solve it with a linear time
def FindUniqueNumber(nums):
res = 0
memo = {}
for i in nums:
if not memo .get(str(i)):
memo [str(i)] = 1
res +=i
else:
res -=i
return res