Finding The Lonely Integer Using XOR and JavaScript

The Lonely Integer problem is a classic beginner coding question and one often found on HackerRank tests and in interviews. The problem is this: given an array of integers, find the unique integer. The array will be at least one integer and will always have a unique integer. In this article I will cover the process of reasoning out a solution, a dynamic programming solution, the XOR solution and finally how binary numbers and XOR works. Click on any of the lines below to scroll to the part you’re most interested in.

Reasoning Out an Unfamiliar Problem

Dynamic Programming Solution

Solution Using XOR

How Binary and XOR Works

Reasoning Out an Unfamiliar Problem

In order to solve this problem, there are many options. Some better than others. Trying to reason out how to solve this problem knowing no special tricks, I default to thinking “how would I solve this by hand?” This line of thinking is a good way to come up with a solution if you can’t think of how to start.

If I was going to solve this by hand and the array was long enough that I wouldn’t be able to remember which numbers I’ve already counted, I would have to write things down. I would make a new list, each entry with a number I’ve counted and the times I’ve counted it. That way when I was finished going through the array, I could find the number that was only counted once.

Dynamic Programming Solution

Putting that answer into programming terms, first check if the array is one element and return that (unique) element. Otherwise create an object named count. Then iterate through the array, checking if the number in the array is already a key in count. If it’s not a key, create a new key with that number with a value of 1. If the array value is already a key, then increment its value by 1. After finishing iterating through the array, iterate through the count object and return the key with the value of 1.

Put into javascript it would look like this:

This solution has a linear runtime complexity or O(N). This is because even though there are two loops used, one to iterate through the array and another to iterate through the object, those loops are not nested and runtime would technically be O(2N). Big O notation simplifies down 2N to just N. That being said, there is still room for improvement. Or, at least a more elegant solution exists.

Solution Using XOR

There is a way to solve Lonely Integer with something called bitwise operations. Specifically the XOR operator or ^ in JavaScript. XOR stands for exclusively or. That means at a simple level, if the numbers on both sides are the same, it returns zero. If one side is zero then it will return the non-zero number. If two numbers are different and non-zero, it will return a bit-manipulated number. You don’t need to understand how exactly the bit manipulation works for this problem, just that it will preform the same operation every time. I will provide a more in-depth explanation at the end of this article if you want deep understanding.

Here is the solution using XOR:

Wonderfully compact.

To get a better idea of what is happening, below are some examples. These demonstrate how the XOR reduce function handles each step for evaluating various arrays that have the unique number at different indexes.

Example 1: [0,1,1,0,7]

0 ^0 = 0

0 ^ 1= 1

1 ^ 1= 0

0 ^ 0= 0

0 ^ 7= 7

Example 2: [8,0,0]

0 ^ 8 =8

8 ^0 = 8

8 ^ 0=8

Example 3: [10,4,5,4,5]

0 ^ 10 = 10

10 ^ 4= 14

14 ^ 5= 11

11 ^ 4= 15

15 ^ 5= 10

Because of how the reduce function works, it will always start at zero and XOR it with the first index of the array (or the 0th index to be precise). The function takes the value from the previous step and XOR’s it with the next value of the array until it has gone through each element.

How Binary and XOR Works

For a complete understanding, I will cover how binary numbers work. Starting from the first digit on the right, it represents 1. With one bit, you can get 1 or 0. The second digit represents 2. With 2 bits you can get 1, 2 or 3.

1 -> 01

2 -> 10

3 -> 11

The next digit to the left represents 4 or rather 2². Each digit further to the left is one more power of 2.

With an understanding of binary numbers, it’s easy to see how XOR works exactly with numbers. It compares each bit of the two numbers. If the bits are the same, it returns zero. If they differ, the return bit is 1. Here is a demonstration of 15 ^ 5=10 in 4 bits:

5 -> 0101

15-> 1111

10-> 1010

I hope this article increased your understanding of how XOR and binary work. There are some cool bit manipulation applications out there and it can be a helpful card to have up your sleeve in solving algorithm problems.

I write about programming and specifically CSS | HTML | JavaScript | Ruby | React.js | Redux.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store