Finding the stray number in an array using XOR

Suppose we have an array like this:

int arr[5] = { 3, 3, 6, 4, 4 };

Our goal is to find the stray number. The stray number is a number which does not have a duplicate. Thus, it has a length of 1. In our example it’s 6.

We can use XOR bitwise operation for this purpose. Here is an example of how XOR works.

bit abit ba ^ b (a XOR b)
000
011
101
110

XOR returns 1 if the bits are different otherwise returns 0. Look at this example as well. Here the numbers are the same.

bit abit ba ^ b (a XOR b)
000
110
110
110

You can see that the XOR basically cancels out the numbers. Therefore we can loop through our array and apply XOR to every element like this:

int arr[5] = { 3, 3, 6, 4, 4 };
int sum = 0;

for(int i = 0; i < 5; i++)
     sum = sum ^ arr[i];

printf("%d", sum); // => 6

There can also be a case when there is no stray number. We can check it like this:

int arr[5] = { 3, 3, 6, 4, 4 };
int sum = 0;

for(int i = 0; i < 5; i++)
     sum = sum ^ arr[i];

if(sum != 0)
    printf("%d", sum); // => 6
else
    printf("No stray number"); 

But there is a small bug in this code. If the sum equals zero at the end we don’t know whether there is no stray number or the stray number is zero. We can solve this problem by counting the zeros in our array. Otherwise ff the final count is odd that means the stray number is zero. If the count is even the stray number is not zero.

Final code:

int arr[5] = { 3, 3, 6, 4, 4 };
int sum = 0;
int zeroCount = 0;

for(int i = 0; i < 5; i++) {
     if(arr[i] == 0)
          zeroCount++;
     sum = sum ^ arr[i];
}

if(zeroCount % 2 != 0 || sum != 0)
    printf("%d", sum); // => 6
else
    printf("No stray number"); 

Leave a Reply

Your email address will not be published. Required fields are marked *