find the only unpaired element in the array

Accenture interview question:

You have been given an array of size 2n+1 that have n pair of integers (can be +ve, -ve or开发者_如何学Go 0) and one unpaired element.

How would you find the unpaired element?

Pair means duplicate. So (3,3) is a pair and (3,-3) is not a pair.

---

Take XOR of all the elements.

The pairs will cancel out as

a XOR a = 0

and the result will be the only unpaired element as

0 XOR a = a

If its okay to destroy the array you can XOR adjacent elements. Once done the last element of the array has the unpaired element:

N = Num of elements in array.
for( i=1 to N )
   arr[i] ^= arr[i-1];    
print arr[N-1]

If its not okay to destroy the array, you can make use of a variable to hold the result:

N = Num of elements in array.
Unpaired = arr[0];
for( i=1 to N )
   Unpaired = Unpaired ^ arr[i];    
print Unpaired

C function to do the same:

int findUnpaired(int *arr,int len) {
 int i;                  // loop counter.
 int unpaired;           // to hold the unpaired element.

 unpaired = arr[0];      // initialize it with the 1st array ele.

 for(i=1;i<len;i++) {    // loop for all remaining elements.
    unpaired ^= arr[i];  // XOR each element with the running XOR.
 }
 return unpaired;        // return result.
}

---

Alternate solution, to find all unique values in O(n) and O(n) space:

Initialize a Hash table.
For each value in the array, check if the value exists in the Hash table, if it does, remove it, if it doesn't, add it.
Return value is all the items inside the Hash table.

Can easily be modified to use a dictionary if the recurring values can recur more than once.

---

Single line Linq example with a XOR solution :

Demo on DotNetFiddle

public static void Main()
{
    int[] tab = { 1, 2, 3, 2, 1 };
    Console.WriteLine(GetSingle(tab));
}

private static int GetSingle(IEnumerable<int> tab)
{
    return tab.Aggregate(0, (current, i) => current ^ i);
}

For fun and profit

Edit:

Explication for this snippet.

var a = 2;
var b = 2;
Console.WriteLine(a ^ b); // will print 0
// because x ^ x == 0

var c = 3;
Console.WriteLine(a ^ b ^ c); // will print 3
// because 0 ^ x == x

Console.WriteLine(0 ^ a); // guess the output
// get it? :)
// Now, lets aggregate this enumerable ;)

---

The best answer is the XOR operator. Just for fun another way is, if you are allowed to sort the array, to sort it and compare adjacent integers. This assumes all integers appear exactly twice with one integer appearing once.

// Random array of integers
int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// Sort the array.
Arrays.sort(arr);

// Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 
// Cycle through array comparing adjacent values.
for(int i = 0; i < arr.length; i++){

    // This would mean the single number was the last element in the array.
    if(i == arr.length-1)
        singleNum = arr[i];

    // If the adjacent elements are the same, skip foward. 
    if(i < arr.length-1 && arr[i] == arr[i+1])
        i ++;
    else
        // Otherwise, you found the single number.
        singleNum = arr[i];
}

---

Perform XOR among all elements of the given array

def unpaired(arr):
    result = 0
    for i in arr:
        result = result^i
    return result

---

Here'a a simple LINQ solution that can easily be extended to provide the number of occurrences of each unique element:

     int[] numbers = { -1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 };

     var numberGroups =
         from n in numbers
         group n by n into g
         select new { Number = g.Key, IsPaired = g.Count() == 2 };

     Console.WriteLine("Unpaired elements:");
     foreach (var group in numberGroups)
     {
        if (!group.IsPaired)
           Console.WriteLine(group.Number);
     }

Output:

Unpaired elements:
-1
0
5

---

Best solution using JavaScript, took me some time.

    var singleNumber = function(nums) {
       return nums.reduce((a,b) => a^b);
    };

Using reduce, code will add all of the numbers cumulatively, but since the pars (a, b) using XOR cancel each other out, only the number without the par will be returned.

---

It's a good solution too. In this example, we have one cycle passage.

function getUpaired(arr) {
    var obj = {};
    for (var i = 0; i < arr.length; i++) {
        if (typeof obj[arr[i]] !== 'undefined') {
            delete obj[arr[i]];
            continue;
        }
    obj[arr[i]] = i;
    }
    return Number(Object.keys(obj)[0]);
}
getUpaired([0,0,2,1,3,2,1]);

---

If you are using Swift you can find unpaired element with following code

func findUnpaired(_ arr: [Int]) -> Int {
    return arr.reduce(0, +)
}

---

A java solution of the above question:

public int singleNumber(int[] nums) {
    int result = nums[0];
    for(int i = 1; i < nums.length; i++) {
        result = result^nums[i];
    }
    return result;
}