Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
xor
communitycreator

Use XOR in C++ to find the non-repeating element in an array

Harsh Jain

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 O(NLogN)O(NLogN) time. We need to think about some approach that would solve this problem in O(N)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.

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;
}
Find the non-repeating element in the array - Solution

Explanation

  • In line 6, we create an array with some integer elements.
  • In line 8, we initialize the result as 0.
  • 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 O(N)O(N) time and constant space.

RELATED TAGS

c++
xor
communitycreator
RELATED COURSES

View all Courses

Keep Exploring