Codility 'OddOccurrencesInArray' Solution

Martin Kysel · December 11, 2014

Short Problem Definition:

Find value that occurs in odd number of elements.



expected worst-case time complexity is O(N)

expected worst-case space complexity is O(1)


This problem can be found in many algorithm books. A xor A cancels itself and B xor 0 is B. Therefore A xor A xor B xor C xor C is B.


def solution(A):
    missing_int = 0
    for value in A:
        missing_int ^= value
    return missing_int

Twitter, Facebook