Find a special number in an array

Question

There are many numbers in an array and each number appears three times excepting for one special number appearing once. Here is the question: how can I find the special number in the array?
Now I can only put forward some methods with radix sorting and rapid sorting which cannot takes advantage the property of the question. So I need some other algorithms.
Thanks for your help.

Answer 1

Add the numbers bitwise mod 3, e.g.

def special(lst):
    ones = 0
    twos = 0
    for x in lst:
        twos |= ones & x
        ones ^= x
        not_threes = ~(ones & twos)
        ones &= not_threes
        twos &= not_threes
    return ones