Use XOR in C++ to find the non-repeating element in an array
Problem statement
We are given an array in which all the numbers except one are repeated once. In other words, there are 2N + 1 numbers in the array where N numbers occur twice in the array. We need to find that number that occurs only once in the array.
Possible approaches
-
We can sort the array and then check which element occurs once. But, this would take time. We need to think about some approach that would solve this problem in time.
-
We can use the XOR operation to solve this problem. The XOR operation has a property such that if you XOR a number with itself, the answer becomes zero. So, we can do the XOR of all the elements in the array one by one, and then the final result would be our number that occurs once in the array.
Let’s use an example to understand this better.
Suppose the array contains [1, 1, 3, 2, 4, 2, 3]. Now, we follow the steps below.
-
Initialize the XOR result as 0 (
result = 0). -
Pick one element from the array and perform the XOR of that element with
result. -
Continue the steps above until all the elements in that array are processed.
-
At the end, the
resultwill contain the number that occurs once in the array.
Code solution
Let’s look at the code below to make this more clear.
#include <iostream>using namespace std;int main() {int arr[] = {1,1,3,2,4,2,3};int size = sizeof(arr)/sizeof(int);int result = 0;for(int i =0 ; i < size; i++)result = result ^ arr[i];cout << "Number occurs once: " << result;return 0;}
Explanation
- In line 6, we create an array with some integer elements.
- In line 8, we initialize the
resultas0. - In lines 10 and 11, we run a loop to pick one element from the array and perform XOR with the
result. - Finally, in line 13, we print our answer, i.e., the number that occurred once in the array.
In this way, we can use the XOR operation to solve this problem in time and constant space.
