10
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ You could drop the .ToDictionary call, since you are simply enumerating the results afterward. \$\endgroup\$ – Dan Lyons May 17 '16 at 18:18
24
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Genius! Simple and elegant solution. Bonus points for LINQ one-liner. \$\endgroup\$ – Xiaoy312 May 17 '16 at 20:01
  • 2
    \$\begingroup\$ In addition to the fact that a xor a is 0 you also need that xor is assosiative and comutative. \$\endgroup\$ – Taemyr May 18 '16 at 4:39
  • 1
    \$\begingroup\$ One thing to note with the XOR solution is that it's impossible to detect malformed input and will result in garbage if the array doesn't conform to the single unpaired value specification. It's still elegant though! \$\endgroup\$ – RobH May 18 '16 at 8:56
  • \$\begingroup\$ Great, the exclusive or did the job \$\endgroup\$ – Siobhan May 18 '16 at 19:19

protected by Vogel612 Mar 21 at 12:20

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.