Filtering out a stray number in an array
Sung M. Kim Originally published at slightedgecoder.com on ・3 min read
I solved a CodeWars (programming challenge site) question and compared my answer to other solutions.
I was introduced to a different way of solving a question with a boolean operation.
Be prepared to be blown away.
SPOILER ALERT! : Answers are shown below so proceed at your own discretion (or try to solve the question yourself first before proceeding to compare your answer)
Question Detail
The question, Find the stray number, requires you to find a number in an oddlength array of numbers. There is only one element with length one.
As an example, suppose that there is an array, int[] a = {1, 1, 2, 2, 3}
and the stray number is 3
because 1
and 2
have an even length.
Typical Implementation
One would usually approach the problem by counting number of each element and find the one with odd count.
Here is my implementation submitted on CodeWars.
The code above gets a count of each element(GroupBy
then Select
) and returns an item with an odd number of counts (o.Count % 2 == 1
).
When your answer is accepted on CodeWars, you can see solutions posted by others.
Then I spotted a oneliner using a XOR (Exclusive OR) bitwise operation by Unnamed (that’s a user ID).
Note that,

.Aggregate
in C# is to Array#reduce in Javascript as 
.Select
is to Array#map
How does that work?
If you have been programming, you might have seldom used XOR. But to recap, XOR returns true if two inputs being compared are different (Wikipedia).
So for an even number of elements, they will all come out as 0 (false) and be left with the value of one element (true).
To visualize what’s going on, I created a simple program below.
It’s just an iterative version of the oneliner answer by Unnamed.
So for two arrays, a1
& a2
above, n1
would print 2 and n2
, 3.
I’ve added WriteLine
to show what is going on more visually.
Note : Numbers in parenthesis are binary representations.
As you can see, even number elements are canceling each other out and what’s left is the stray number.
XOR trick work for an oddlength array where all other elements have even length and there is only one stray number.
E.g.) For an array “int[] a = {1, 1, 2, 2, 3}”, Stray(a)
would return 3.
Conclusion
I hope you were surprised if you had solved the question before proceeding. It’s just surprising how a simple boolean operation can be used to solve a seemingly unrelated problem.
But be aware that the oneliner was clever but it might cause too much cognitive load thus might not be readable.
P.S.
Would you share any other use cases that you have found for XOR or boolean/bitwise operations?
The post Filtering out a stray number in an array appeared first on Slight Edge Coder.
That's a great work around.
Would you be able to do it in
O(n)
time?numbers.sort
usually beO(n log n)
(unless using TimSort and data is already sorted).