Find the Unique Number in an Array: Using the XOR operator
A walkthrough on how to solve a single number locater algorithm question using the handy XOR operator in JavaScript
Welcome to the world of data structures algorithms, reader.
Coding bootcamps are a past now, but we’ve been introduced to this cruel but fascinating world. I’ve quickly developed a love-hate relationship in solving algorithm questions — I’ve spent the last couple of weeks being introduced to different algorithm patterns and complex problems on the web, most notably Leetcode.
I hate it because it’s such a humbling experience tackling each problem (and often times I question my ability & confidence), but I love it because each problem offers a opportunity to learn something new — a new way to use a method, tips & tricks on how to write my logic, and ultimately becoming a better programmer. It seems like each creative solution to a problem easily blew my mind.
Want to read this story later? Save it in Journal.
And this problem was no different.
One of the first algorithm problems I tackled on Leetcode asked for me to find the unique number in an array. The problem was stated as follows:
Write a function where given a non-empty array of integers nums, every element appears twice except for one. Find that single one. FOLLOW UP: Could you implement a solution with a O(N) time complexity and without using extra memory?
OK. As I typically do prior to jumping right into coding, I took a step back & mapped out the steps & thought of what possible problem solving patterns I could use. With my limited knowledge of algorithm problem solving, I’ve only been introduced to a few methods, and one of them was a frequency counter approach. I quickly concluded that this will be my best approach to this problem, where I would:
- Create an empty object & set it to a variable
- Set each number in the array as a key in the newly created object. The value will be the number of times it appears in the array.
- Find the key that has a value of one
I felt like a rockstar. Simple & clean…or so I thought.
The problem asks whether we can implement a solution without any extra space complexity. While my approach might be readable, it’s definitely not the most efficient answer.
I took a look on the discussion board for a more efficient approach & came across this gem:
That’s it. This one line of code just ate my 10 lines of code like they were Pringles chips. I remember thinking to myself, what the hell is that?
The XOR operator
Before I move forward with what that brilliant line of code is doing, it’s important to quickly discuss what the XOR operator is.
The XOR operator, or Exclusive Or, is defined by Techopedia as “a logical operator which results true when either of the operands are true (one is true and the other one is false) but both are not true and both are not false.”
Techopedia continues to say that “the simple ‘or’ is a bit ambiguous when both operands are true. Because in that case it is very difficult to understand what exactly satisfies the condition. To remove this ambiguity, the “exclusive” term has been added to “or” to make it more clear in meaning.”
So it removes the ambiguity of the OR operator. But how does it solve our problem?
That’s where the magic of the XOR operator being used with the reduce method happens.
Binary XOR Operation
Under the hood, the XOR operator is converting each number to its binary equivalent.
If you’re wondering what binary numbers are, here’s a great article that introduces you to this topic: https://www.thoughtco.com/what-is-binary-2694150
The binary XOR operation has two inputs and one output, similar to the add operation which takes in two arguments and produces one result. However, the inputs to a binary XOR operation can only be a 0 or 1, and the result can only be a 0 or 1.
The binary XOR operation (also known as the binary XOR function) will always produce a 1 output if either of its inputs is 1 and will produce a 0 output if both of its inputs are 0 or 1.
To illustrate this point, lets say we have inputs X and Y and the output is Z, the XOR function will be as follows:
With this in mind, we now understand what’s happening under the hood of this operation. So let’s wrap it up by reviewing it with our original problem!
Bringing it home
Now that we know what’s happening with binary XOR operation, let’s use a test case with our original problem and look at each step:
Based on our test case, our expected output should be 7. Let’s take a closer look as to what’s happening.
The reduce method is iterating through each of our number, starting with our previous number and comparing it to our current number. During our first iteration, our XOR operator is looking at 5, or “1, 0, 1” as our previous number and 4, or “1, 0, 0”, as our current number. Using the rules of our Binary XOR operation above, our output is “0, 0, 1” and this new binary number becomes our previous number, and we then move on to the next iteration and compare 5, or “1, 0, 1” to it. This behavior continues until we finally reach our output, which is our expected 7, or “1, 1, 1”
Conclusion
Brilliant, right? It can be daunting at first when we find solutions that are so much more intuitive than ours. It’s a humbling experience, but once we find out how each operates under the hood, our minds will slowly develop, and perhaps one day we’ll develop our own one-liners to show off to the world.
While this was my first experience encountering the XOR operator, I look forward to more instances where it can be utilized in applications and algorithm questions.
Sources
Techopedia: Exclusive OR (XOR) https://www.techopedia.com/definition/3472/exclusive-or-xor
ThoughtCo: Reading and Writing Binary Numbers https://www.thoughtco.com/what-is-binary-2694150
📝 Save this story in Journal.
