Programming Interview Questions 18: Find Even Occurring Element

Given an integer array, one element occurs even number of times and all others have odd occurrences. Find the element with even occurrences.

We can use a hashtable as we always do with problems that involve counting. Scan the array and count the occurrences of each number. Then perform a second pass from the hashtable and return the element with even count. Here’s the code:

def getEven1(arr):
    counts=collections.defaultdict(int)
    for num in arr:
        counts[num]+=1
    for num, count in counts.items():
        if count%2==0:
            return num

Time and space complexity of this approach is O(N), which is optimal. There’s also another equally efficient but more elegant solution using the XOR trick I explained in my previous post find missing element. First we get all the unique numbers in the array using a set in O(N) time. Then we XOR the original array and the unique numbers all together. Result of XOR is the even occurring element. Because every odd occurring element in the array will be XORed with itself odd number of times, therefore producing a 0. And the only even occurring element will be XORed with itself even number of times, which is the number itself. The order of XOR is not important. The conclusion is that if we XOR a number with itself odd number of times we get 0, otherwise if we XOR even number of times then we get the number itself. And with multiple numbers, the order of XOR is not important, just how many times we XOR a number with itself is significant.

For example, let’s say we’re given the following array: [2, 1, 3, 1]. First we get all the unique elements [1, 2, 3]. Then we construct a new array from the original array and the unique elements by appending them together [2, 1, 3, 1, 1, 2, 3]. We XOR all the elements in this new array. The result is 2^1^3^1^1^2^3 = 1. Because the numbers 2 and 3 occur in the new array even number of times (2 times), so they’ll be XORed with themselves odd times (1 time), which results in 0. The number 1 occurs odd number of times (3 times), so it’ll be XORed with itself even times (2 times), and the result is the number 1 itself. Which is the even occurring element in the original array. Here’s the code of this approach:

def getEven2(arr):
    return reduce(lambda x, y: x^y, arr+list(set(arr)))

Time and space complexity of this approach is also O(N). Note that I assume O(1) insert and find in both hashtable and set, which is mostly the case in the average. But the actual worst case complexity depends on the implementation and the programming language used. It can be logarithmic, or even linear. But in an interview setting I think it’s safe to assume constant time insert and find in both hashtable and set.

VN:F [1.9.22_1171]
Rating: 8.6/10 (20 votes cast)
Programming Interview Questions 18: Find Even Occurring Element, 8.6 out of 10 based on 20 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • Ibby

    We can use a hashtable as we always do with problems that involve counting. Scan the array and count the occurrences of each number. Then perform a second pass from the hashtable and return the element with even count.

    Can’t we just pass the array once?
    Use a hashMap to store the elements as a key and their count as values.
    Run through the array once, do a map.get on the element, if value is null put it in the map, if value != NULL it means the element has been added before and output it as the element occurring two times and break the loop.
    Worst case if all elements are odd…Ɵ(N).
    Best Case anywhere in O(N), the earlier we hit the even element, the earlier the loop breaks.

    • Arden

      “if value != NULL it means the element has been added before and output it as the element occurring two times and break the loop.”

      How do you know that element won’t occur in the array later? Even occurrence doesn’t mean only 2 occurrences, it can be any even number. And odd occurrence doesn’t necessarily mean 1, can be any odd number.

      • Ibby

        Aye doesn’t make sense, My bad, have to go through the whole array once.

  • Moe

    Hi Guys,

    I have been asked this question. what data structure do you use to store US SSN.
    Then write a function that takes a user input (SSN). If the entered SSN is available, return True, else return the nearest available SSN. Any Thought ??

    • Arden

      I would consider using the Trie data structure. Lookup complexity is constant, which is just the number of digits in SSN. Hashtable would also have constant lookup time, but finding nearest SSN would be faster in a Trie since Hashtable doesn’t have any ordering on keys.

  • SJ

    This might look stupid .. but i will still ask.
    I do not understand your comment “First we get all the unique numbers in the array using a set in O(N) time”. How are you getting this unique number set, could you explain?

    Also, great site and very helpful explanations !

    • Arden

      Add all the numbers to the set, since sets contain only unique elements by definition, we obtain the unique numbers. Adding an element to a set can be done in constant time as well.

      • Vamsi

        Can you elaborate on how you can insert into a set in constant time? Or more specifically, can you elaborate what a set is? If you consider a set to be a balanced BST, it should take O(log N) time. Thanks in advance.

  • sonesh

    How do you get distinct element in (N)
    Please if you are using some library or anythings, mansion the complexity of that, without assuming that you have done some sort of pre-processing, like here suppose you have given an array, now you tell ??

  • baris evrim demiroz

    If we want to detect the existence of an element that occurs even number of times using the XOR approach, we can define two `result` variables initialized with different values and check if they are equal at the end.

  • Architect


    //Java 8 Streams & Lambdas solution by the Architect https://disqus.com/by/op8rv315/
    List numberList = new ArrayList(Arrays.asList(2, 1, 3, 1));

    numberList.addAll(new HashSet(numberList));
    Optional dupe = numberList.stream()
    .reduce((x, y) -> x^y);
    System.out.println(dupe.get());