I was spending some time on codewars, and came across an exercise that asked for:
Given an array, find the
int
one that appears an odd number of times.There will always be a single integer that appears an odd number of times.
I solved it using GroupBy
but looking at all the answers, one was the following:
public static int find_it(int[] seq)
{
int found = 0;
foreach (var num in seq)
{
found ^= num;
}
return found;
}
example case
var result ; find_it(new[] { 20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5 })
//result vale 5.
It caught my attention, because I had never used the operator ^=
, so I began to debug and try to understand it, but without success.
found
I don't understand how precisely the number that appears an odd number of times ends up in the variable .
Could someone explain to me how it works?
The ^ operator is the binary exclusive OR operator. In the case of comparison between integers (like yours) it compares the values bit by bit and returns 0 if the bits are equal or 1 if they are different. In your case, use it together with the assignment operator, that is:
It ends up being the same as:
In your vector you will have a single number that is repeated an odd number of times, the rest will always be even repetitions. Let's give an example with a small vector so it is understood:
As I said before, in integers the comparison is bitwise. In the first iteration it compares the 0 with the 2, in binary:
The result will be:
In the second iteration the previous result with the 5:
Result:
Now follows a 1:
Result:
Fourth iteration again 1:
Result:
And the last iteration on 2:
Final score:
Which in decimal is 5, precisely the only number that is repeated an odd number of times.
For better understanding, when an Exclusive OR is done between 2 equal values, the result will always be 0. And when you compare 0 with X, the result will always be X. Then, the values of even repetitions will always cancel each other, leaving as result 0. In the end, this zero will be compared with the only value that is left over (because it is an odd repetition), and therefore the result will be that value. This is always the case, regardless of the order of these values.
I leave you the official documentation of said operator: https://docs.microsoft.com/es-es/dotnet/csharp/language-reference/operators/xor-operator