Find single in an array of 2n+1 integer elements
Given an array with 2n+1 integers, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.
Input : { 1, 1, 2, 2, 3, 3, 4, 4, 5} Output : 5 Input : { 7, 9, 6, 8, 3, 7, 8, 6, 9} Output : 3
The idea is to do XOR of all elements. XOR of all elements gives us the result. The idea is based on below XOR properties.
 XOR of a number with itself is 0.
 XOR of a number with 0 is the number.

// CPP program to find only element in an array
// where every element appears twice.
#include <bits/stdc++.h>
using
namespace
std;
/* Find non repeating number in an array */
int
findNonRepeating(
int
arr[],
int
n)
{
int
res = 0;
for
(
int
i = 0, res = 0; i < n; i++)
res = res ^ arr[i];
return
res;
}
/* Driver program */
int
main()
{
int
arr[] = { 3, 8, 3, 2, 2, 1, 1 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
cout << findNonRepeating(arr, n);
return
0;
}
Output:
8
Time Complexity: O(n).
Space Complexity: O(1).
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide