Find the odd occurrences in an array

Question

Recently, I came across this problem on Codility. I am aware there is a bit of similarity to this question and this question, but I am trying to achieve this in C#.

The problem is as follows:

A non-empty zero-indexed array \$A\$ consisting of \$N\$ integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array \$A\$ such that:

\$\begin{align} & A[0] = 9, A[1] = 3, A[2] = 9 \\ & A[3] = 3, A[4] = 9, A[5] = 7 \\ & A[6] = 9 \end{align}\$

• The elements at indexes 0 and 2 have value 9
• The elements at indexes 1 and 3 have value 3
• The elements at indexes 4 and 6 have value 9
• The element at index 5 has value 7 and is unpaired

Write a function:

class Solution { public int solution(int[] A); }

that, given an array \$A\$ consisting of \$N\$ integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array \$A\$ such that:

\$\begin{align} & A[0] = 9, A[1] = 3, A[2] = 9 \\ & A[3] = 3, A[4] = 9, A[5] = 7 \\ & A[6] = 9 \end{align}\$

the function should return 7, as explained in the example above.

Assume that:

• \$N\$ is an odd integer within the range \$[1 \dots 1,000,000]\$
• Each element of array \$A\$ is an integer within the range \$[1 \dots 1,000,000,000]\$
• All but one of the values in \$A\$ occur an even number of times.

Complexity:

• Expected worst-case time complexity is \$O(N)\$
• Expected worst-case space complexity is \$O(1)\$, beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

I came up with a dictionary with the unique numbers as the key and the frequencies as the value and used Linq to filter the even numbers. Indirectly this means that a number divisible by 2 would have a pair. So far the code performs well, but I believe there is room for improvement as my performance was \$O(N)\$ and also out of curiosity how does Linq achieve better performance than the loops (e.g for).

    public static int OddOccurrencesInArray(int[] A)
    {
        Dictionary<int, int> dictionary = new Dictionary<int, int>();
        foreach(var item in A)
        {
            if (!dictionary.ContainsKey(item))
            {
                dictionary.Add(item, 1);
            }
            else
            {
                dictionary[item]++;
            }
        }
       var query = dictionary.Where(k=>(k.Value % 2) != 0).ToDictionary(k=>k.Key, k=>k.Value);

        foreach(var p in query)
        {
            return p.Key;
        }

        return 0;     
    }
    static void Main(string[] args)
    {
        int[] A = { 9, 3, 9, 3, 9, 7, 9};
        Console.WriteLine(OddOccurrencesInArray(A));
        Console.ReadLine();
    }
}

Answer 1

There is a simple solution that does not require a dictionary:

int[] A = { 9, 3, 9, 3, 9, 7, 9};
int result = 0;
foreach (var i in A)
    result ^= i;
Console.WriteLine(result); // 7

The trick here is, that "a xor a" gives 0. So all number will be erased except the single one.

---

Or in short:

var result = new [] { 9, 3, 9, 3, 9, 7, 9}.Aggregate(0, (a, b) => a^b);

---

To you solution with the dictionary:

You don't need a dictionary. You could just use a Hashset. Add a new entry if the entry does not exists and remove the entry if it already exists. After processing all items, the hashset should have one item - the result.