Given an array of integers with all its elements between 1 to n with the exception of two elements which occur twice. Find two duplicate elements without using any extra memory.

Expected time complexity: O(n)

For example,

**Input: **arr = [4, 3, 6, 5, 2, 4, 1, 1]

** Output: **Duplicate elements are 1 and 4

**Related Posts: **Find two odd occurring element in an array without using any extra space

We can use hashing to solve this problem in O(n) time. The idea is to traverse the array and maintain frequency of each element in a hash table. Then after all array elements are processed, we return the elements with frequency of two. The problem with this approach is that it requires O(n) extra space as well. Also it requires one traversal of array and one traversal of hash table. The advantage of this approach is its simplicity and the fact that it will work for any number of duplicates elements present in the array.

We can solve this problem in one traversal of array and in O(1) space. The idea is to use **XOR operator**. We know that if we XOR a number with itself odd number of times the result is number itself, otherwise if we XOR a number even number of times with itself, the result is 0. Also XOR with 0 is always the number itself.

XOR x with 0

x ^ 0 = x

XOR x with itself even number of times

x ^ x = 0

x ^ x ^ x ^ x = (x ^ x) ^ (x ^ x) = 0 ^ 0 = 0

XOR x with itself odd number of times

(x ^ x ^ x) = (x ^ (x ^ x)) = (x ^ 0) = x

(x ^ x ^ x ^ x ^ x) = (x ^ (x ^ x) ^ (x ^ x)) = (x ^ 0 ^ 0) = x

So, if we take XOR of all elements present in the array with every element in the range [1 .. n], even appearing elements will cancel out each other and we are left with XOR of x and y (x ^ y) where x and y are two duplicate elements. Note that the duplicate elements will be XORed 3 times in total, whereas all others elements will be XORed twice.

##### How to find x and y?

res = (x ^ y)

We know that any set bit in *res* will be either set in x or y (but not in both as a bit will only set in *res* when it is set in one number and unset in the other).

The idea is to consider the rightmost set bit in *res* (or any other set bit) and split the array/range into two lists –

- First list contains all elements of the array and numbers in range that have this bit set.

- Second list contains all elements of the array and numbers in range that have this bit unset.

As this rightmost bit is set in one number and unset in the other, we will have one duplicate element in each list. Basically we have isolated trait of one number with other so that both x and y will go to different lists.

Now we iterate each list once more, do XOR on each element of the list and the result will be the duplicate element present in that list (since elements appearing twice will cancel each other).

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <math.h> using namespace std; // Function to find two repeating elements in an array of size n+2 // having range of elements between [1 to n] using XOR operator pair<int, int> findDuplicates(int arr[], int n) { // take XOR of all array elements from index [0 to n-1] and // all numbers in range [1 to n] int res = arr[0] ^ arr[n+1]; for (int i = 1; i <= n; i++) res = res ^ arr[i] ^ i; // x and y are two duplicate elements int x = 0, y = 0; // res stores (x ^ y) // find position of the rightmost set bit in res int k = log2(res & -res); // split the array into two sub-arrays for (int i = 0; i < n + 2; i++) { // array elements that have k'th bit 1 if (arr[i] & (1 << k)) x = x ^ arr[i]; // array elements that have k'th bit 0 else y = y ^ arr[i]; } // split the range [1-n] into two sub-range for (int i = 1; i <= n; i++) { // number i have k'th bit 1 if (i & (1 << k)) x = x ^ i; // number i have k'th bit 0 else y = y ^ i; } return make_pair(x, y); } // Find two duplicate elements in an limited range array int main() { int arr[] = { 4, 3, 6, 5, 2, 4, 1, 1 }; int n = 6; // size of the array is n + 2 pair<int, int> p = findDuplicates(arr, n); cout << "Duplicate elements are " << p.first << " and " << p.second; return 0; } |

`Output:`

Duplicate elements are 1 and 4

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply