Find the Unique Element that Appears k Times in an Array

Problem: Let's first come with some special cases of this problem. Then we can generalize. Given an integer array, only one integer appears 2 times, all the other integers appears 3 times in the array. Find out that integer. For example, for a[] = [2,3,2,4,4,2,3,4], the output should be "3".

Solution: Definitely with hash table or sorting, the problem can be easily solved. What if those approaches are not allowed? Fortunately, we can still use bit operation to solve this problem.

• We need some counters to store the bits that just appear once, the bits that appear twice.
• If some bit appear three times, we need to reset those counters.
• Then at the end, the counter that stores the bits that appear twice will be the answer

Sample code is as follow:

def foo(list):
        # three counters which are used to store
        # the bits that appear 1 time, 2 times and 
        # three times, respectively
        ones = 0
        twos = 0
        threes = 0

        for x in list:
                # which bits had appeared for 3 times?
                # and later we need to reset those
                # bits if they also appear in the 
                # counter "ones" and "twos".
                threes = twos & x
                twos ^= (ones & x)
                twos &= ~threes
                ones ^= x
                ones &= (~threes & ~twos)

        # here we just need to return the counter 
        # "twos". If we need the unique element
        # that appears once (assuming the rest
        # all appear 3 times, just return "ones"
        # instead. 
        return twos

A more general problem: What if we change the problem. Now the problem is given an integer array, only one integer appears k times, all the other integers appears m times in the array (k<m). Find out that integer.

Solution: We can use similar strategy (as shown in above code snippet) to solve the problem.

• Basically, we need m counters (or a counter array). 
• We have counters[m] = counter[m-1] & x.
• counter[i] ^=  counter[i-1] & x and  counter[i] &= (~ counters[m] & ~counters[m-1] & ... &  ~counters[i+1] )