Find the only unpaired element in the array

Question

Question about the interview with Accenture:

You are given an array of size 2n+1 , which has a pair of integers n (maybe +ve , -ve or 0 ) and one unpaired element.

How do you find an unpaired element?

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

Answer 1

Take the XOR all the elements.

Steam will be canceled as

 a XOR a = 0 

and the result will be the only unpaired element as

 0 XOR a = a 

If everything is in order to destroy the array, you can XOR adjacent elements. After execution, the last element of the array has an unpaired element:

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

If you cannot destroy the array, you can use the variable to store the result:

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

C 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. } 

Answer 2

An alternative solution is to find all unique values ​​in O (n) and O (n) space:

Initialize the hash table.
For each value in the array, check if the value exists in the Hash table, if it exists, delete it, if it is not, add it.
The return value is all the elements inside the Hash table.

You can easily change to use the dictionary if duplicate values ​​are repeated more than once.

Answer 3

Linq Linq example with XOR solution:

DotNetFiddle Demo

 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 pleasure and profit

Edit:

Explication for this fragment.

 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 ;) 

Answer 4

The best answer is the XOR operator. Just for fun, another way is if you are allowed to sort the array, sort it, and compare neighboring integers. This assumes that all integers are displayed 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]; } 

Answer 5

Here is a simple LINQ solution that can be easily 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 

Answer 6

Perform an XOR among all the elements in this array

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

Answer 7

This is also a good solution. In this example, we have one loop pass.

 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]); 

Answer 8

Best JavaScript solution, it took me some time.

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

Using the Reduce method, the code will sum all numbers cumulatively, but since pairs (a, b) using XOR mutually cancel each other out, only a number without a face value will be returned.