How to find 2 unpaired elements in an array?

Question

You have an array with n = 2k + 2 elements in which 2 elements do not have a pair. Example for an array of 8 elements: 1 2 3 47 3 1 2 0. "47" and "0" do not have a pair in the array. If I have an array where only one element has a pair, I solve this problem with XOR. But I have two flimsy elements! What can I do? The solution may be for O (n) performance and O (1) extra memory.

Answer 1

Some tips ...

It takes 2 passes. First, browse the list and XOR all items together. See what you get. Move from there.

Edit: A key observation of the result of the first pass should be that it shows you a set of bits in which two unpaired elements are different.

Answer 2

Use INT_MAX / 8 bytes of memory. Go through the array. XOR bit corresponding to each value with 1. If there are 0 or 2 instances, the bit will be 0. If there is only one instance, it will be set. O (1) mem, O (N).

Answer 3

• Scan the array and put each number and count in a hash.
• Repeat the search and find the items with count = 1.

This is O (n).

Answer 4

You can try this.It will take O (n) time

int xor = arr[0]; int set_bit_no; int i; int x = 0; //First unpair number int y = 0; //second unpair number for (i = 1; i < n; i++) xor ^= arr[i]; set_bit_no = xor & ~(xor-1);//Get the rightmost set bit in set_bit_no for (i = 0; i < n; i++) { if (arr[i] & set_bit_no) { //XOR of first set x = x ^ arr[i]; } else { //XOR of second set y = y ^ arr[i]; } } 

Explanation ... arr [] = {2, 4, 7, 9, 2, 4} 1) Get the XOR of all the elements. xor = 2 ^ 4 ^ 7 ^ 9 ^ 2 ^ 4 = 14 (1110) 2) Get a number that has only one bit of the xor bit.
Since we can easily get the rightmost bit, let us use it. set_bit_no = xor and ~ (xor-1) = (1110) and ~ (1101) = 0010 Now set_bit_no will only set the most extreme bit of xor. 3) Now we divide the elements into two sets and make xor of elements in each set, and we get non-repeating elements 7 and 9.