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.

  1. XOR of a number with itself is 0.
  2. 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 growth-oriented 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

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar