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: 7.9/10 (27 votes cast)
Programming Interview Questions 22: Find Odd Occurring Element, 7.9 out of 10 based on 27 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());

  • http://www.nickang.com Nick Ang

    Cool, thanks for explaining this! Jaw dropped when I first saw this solution to the problem.

  • Albert R

    I have a more generalized solution that’s the same time/space complexity. This will work even if there are more than one values in the array an odd number of times.

    You can use the hash method and keep the space complexity constant if you can modify the input array — just pop values. In fact, *total* space starts out as the length of the array (because obviously you need some input), and only decreases from there.


    function solution(A) {
    // store only the elements we've encountered an odd number of times
    var oddElements = {};
    var currentElement;
    var encounteredAnOddNumberOfTimes;

    // iterate over the array, deleting as we go to keep space constant
    while (A.length > 0) {
    currentElement = A.pop();
    encounteredAnOddNumberOfTimes = oddElements[currentElement];

    // if currentVal is true, that means we've encountered that element before
    if (encounteredAnOddNumberOfTimes) {
    delete oddElements[currentElement];
    }

    // otherwise, indicate that we've encountered this element an odd number of times
    else {
    oddElements[currentElement] = true;
    }
    }

    // obviously this return value should be modified if more than one odd value is desired
    return parseInt(Object.keys(oddElements)[0]);
    }

    • Alfonso PD

      At worst case you’ll use n/2 space then it is O(n) space complexity.

      • Albert R

        That’s not accurate, as with popping the input list size is reduced at the same rate or faster than space is used.

        • Alfonso PD

          You’re right, and it seems so in most cases. My first solution was almost the same. However in the worst case (all different paired numbers in the left middle and the other different paired numbers in the right middle) you’ll save the occurrences at achieve the middle position, after pass this you’ll begin to remove the paired numbers, in that case, the odd occurring element is located int the middle :).

  • Dragan Stosic

    scala:

    a.reduceLeft(_^_)

    or using foldLeft

    a.foldLeft(0)((a,b) => a ^ b)