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
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:
const LoneInteger=(array)=>{ if (array.length===1){ return array[0] } let count={} for(let i=0; i<array.length; i++){ if (!count[array[i]]){ count[array[i]]=1 } else { count[array[i]] +=1 } } for (const [key, value] of Object.entries(count)) { if(value === 1){ return key } }}
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:
const XorReduce = (array) => { let a = array.reduce((a,b) => a ^ b,0) return a}
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.
