Programming Interview Questions 22: Find Odd Occurring Element

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

This question is very similar to the previous find even occurring element problem. And we can actually use the same solutions. One approach is again to build a hashtable of element occurrence counts and return the element with odd count. Both time and space complexity of this solution is O(N).

But we can do much better by using the XOR trick described in that post. It’s the following: if we XOR a number with itself odd number of times the result is 0, otherwise if we XOR even number of times the result is the number itself. So, if we XOR all the elements in the array, the result is the odd occurring element itself. Because all even occurring elements will be XORed with themselves odd number of times, producing 0. And the only odd occurring element will be XORed with itself even number of times, producing its own value.

Let’s say we’re given the following array: [1, 2, 3, 1, 2, 3, 1]. If  we XOR all the elements in this array the result is 1^2^3^1^2^3^1 = 1. Because the numbers 2 and 3 will be XORed with themselves 1 time, producing 0. And the number 1 will be XORed with itself 2 times, resulting in its own value. So, the overall result of the XOR operations is the number 1, odd occurring element in the array. Here’s the code:

def getOdd(arr):
    return reduce(lambda x, y: x^y, arr)

Simple as that! The time complexity of this solution is still O(N), but now the space complexity is constant O(1). Because we’re just using constant extra memory, not proportional to the size of the input array. This is the most optimal solution to the problem, since we’re accessing every element only once and using constant extra space.

This is a great question because it demonstrates the power and effectiveness of bit manipulation operators.

VN:F [1.9.22_1171]
Rating: 8.1/10 (26 votes cast)
Programming Interview Questions 22: Find Odd Occurring Element, 8.1 out of 10 based on 26 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • umar

    def getOdd(arr):
    return reduce(lambda x, y: x^y, arr)

    Can u Write above algo in C++.

    what is reduce?

  • http://esteban.kuber.com.ar/resume Esteban Kuber

    Only one caveat: the XOR trick falls apart if you can’t be assured that there is only one odd occurring element or if 0 is a valid input.

    • Arden

      The problem definition ensures that there’s only one odd occurring element. And 0 won’t cause any problems, XORing a number with 0 doesn’t change anything, it just leaves the number as it is.

      • http://esteban.kuber.com.ar/resume Esteban Kuber

        The problem definition ensures that there’s only one odd occurring element.

        I know, but I thought it was worth stating it out loud just in case somebody would miss it :)

        And 0 won’t cause any problems, XORing a number with 0 doesn’t change anything, it just leaves the number as it is.

        How would you differentiate between a return value of 0 because 0 was happening an odd amount of times and a return value of 0 because no values appeared an odd amount of times?

        • Arden

          Good point, thanks for clarifying. The answer lies in problem definition and how much error checking we need. We can return -1 for invalid input. The code ignores this case, and negative and floating point numbers for simplicity. But your comment is definitely worth mentioning to the interviewer.

  • Koray

    What if there were 2 numbers with odd occurrence? Is there any efficient way to solve that problem in better than O(N) too?

  • Architect


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

    Optional odd = numberList.stream()
    .reduce((x, y) -> x^y);

    System.out.println(odd.get());