12
\$\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\$
1
  • \$\begingroup\$ You could drop the .ToDictionary call, since you are simply enumerating the results afterward. \$\endgroup\$
    – Dan Lyons
    May 17, 2016 at 18:18

1 Answer 1

30
\$\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\$
8
  • \$\begingroup\$ Genius! Simple and elegant solution. Bonus points for LINQ one-liner. \$\endgroup\$
    – Xiaoy312
    May 17, 2016 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, 2016 at 4:39
  • 3
    \$\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, 2016 at 8:56
  • \$\begingroup\$ Great, the exclusive or did the job \$\endgroup\$
    – Tolani
    May 18, 2016 at 19:19
  • \$\begingroup\$ @jan, I wrote here a python function that shows ALL odd occurrences using sort() which has O(n*log n). I got 55 % in Codility which is not bad. Would this be another question at CodeReview or should we discuss it here in the comments? My function still can be improved regarding performance. \$\endgroup\$
    – Timo
    Sep 23, 2020 at 7:25

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