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 a | bit b | a ^ b (a XOR b) |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

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

bit a | bit b | a ^ b (a XOR b) |

0 | 0 | 0 |

1 | 1 | 0 |

1 | 1 | 0 |

1 | 1 | 0 |

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");