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.
We can sort the array and then check which element occurs once. But, this would take $O(NLogN)$ time. We need to think about some approach that would solve this problem in $O(N)$ 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 result
will contain the number that occurs once in the array.
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; }
result
as 0
.result
.In this way, we can use the XOR operation to solve this problem in $O(N)$ time and constant space.
RELATED TAGS
CONTRIBUTOR
View all Courses