Filtering out a stray number in an array

javascript, csharp

title: Filtering out a stray number in an array date: "2017-10-07" banner: ./images/Featured-Image-TransmissionCmosXORGate.jpg published_at: "2017-10-07T19:11:33.000Z" tags: "javascript, csharp" author: Sung M. Kim

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.

Question Detail

The question, Find the stray number, requires you to find a number in an odd-length 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.

 public static int Stray(int[] numbers) { return numbers .GroupBy(n => n) .Select(g => new { Key = g.Key, Count = g.Count() }) .Where(o => o.Count % 2 == 1).FirstOrDefault().Key; }
view raw Stray1.cs hosted with ❤ by GitHub

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 one-liner using a XOR (Exclusive OR) bitwise operation by Unnamed (that's a user ID).

 public static int Stray(int[] numbers) { return numbers.Aggregate((a, b) => a ^ b); }
view raw Stray2.cs hosted with ❤ by GitHub

Note that,

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.

 class Program { static void Main(string[] args) { int[] a1 = { 1, 1, 2 }; int[] a2 = { 17, 17, 3, 17, 17, 17, 17 }; n1 = GetStrayNumber(a1); n2 = GetStrayNumber(a2); WriteLine(\$"n1 => {n1}, n2 => {n2}"); } private static int GetStrayNumber(int[] arr) { Func format = n => \$"{n} ({Convert.ToString(n, 2).PadLeft(5, '0')})"; var xor = arr[0]; for (int i = 0; i < arr.Length - 1; i++) { var a = xor; var b = arr[i + 1]; xor = a ^ b; WriteLine(\$"{format(a)} ^ {format(b)} = {format(xor)}"); } WriteLine(new string('=', 80)); return xor; } }
view raw Program.cs hosted with ❤ by GitHub

It's just an iterative version of the one-liner 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.

 1 (00001) ^ 1 (00001) = 0 (00000) 0 (00000) ^ 2 (00010) = 2 (00010) ===================================== 17 (10001) ^ 17 (10001) = 0 (00000) 0 (00000) ^ 3 (00011) = 3 (00011) 3 (00011) ^ 17 (10001) = 18 (10010) 18 (10010) ^ 17 (10001) = 3 (00011) 3 (00011) ^ 17 (10001) = 18 (10010) 18 (10010) ^ 17 (10001) = 3 (00011) ===================================== n1 => 2, n2 => 3
view raw result.cmd hosted with ❤ by GitHub

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 odd-length array where all other elements have even length and there is only one stray number.

E.g.) For an array "int[] a = 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 one-liner 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?