Algorithm to find a number which occurs only once in an array, given all the other numbers occur twice

Question

What I can think of is:

Algo:

1. Have a hash table which will store the number and its associated count
2. Parse the array and increment the count for number.
3. Now parse the hash table to get the number whose count is 1.

Can you guys think of solution better than this. With O(n) runtime and using no extra space

Answer 1

Assuming you can XOR the numbers, that is the key here, I believe, because of the following properties:

• XOR is commutative and associative (so the order in which it's done is irrelevant).
• a number XORed with itself will always be zero.
• zero XORed with a number will be that number.

So, if you simply XOR all the values together, all of the ones that occur twice will cancel each other out (giving 0) and the one remaining number (n) will XOR with that result (0) to give n.

r = 0
for i = 1 to n.size:
    r = r xor n[i]
print "number is " + r

No hash table needed, this has O(n) performance and O(1) extra space (just one tiny little integer).

Answer 2

An answer in Ruby, assuming one singleton, and all others exactly two appearances:

def singleton(array)
  number = 0
  array.each{|n| number = number ^ n}
  number
end

irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3

^ is the bitwise XOR operator, by the way. XOR everything! HAHAHAH!

Rampion has reminded me of the inject method, so you can do this in one line:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

Answer 3

"Parse the array and increment the count for number."

You could change this to "Parse the array and if the number already exists in the hash table, remove the number from the hash table". Then step 3 is just "get the only number that remains in the hash table"

Answer 4

Given an array of integers, every element appears twice except for one. Find that single one. We can use XOR operation. Because every number XOR itself, the results will be zero. So We XOR every integer in the array, and the result is the single one we want to find. Here is the java version code:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}

Follow up 1: Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? For this problem, we can't use the XOR operation.The best way to solve this problem is use "bit count". Create a 32 length int array count[32]. count[i] means how many '1' in the ith bit of all the integers. If count[i] could be divided by 3, then we ignore this bit, else we take out this bit and form the result.Below is java version code:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        int[] count=new int[32];
        for(int i=0;i<32;i++){
            for(int j=0;j<A.length;j++){
                if(((A[j]>>i)&1)==1){
                    count[i]=count[i]+1;
                }
            }
            if((count[i]%3)!=0){
                res=res|(1<<i);
            }
        }
        return res;
    }
}

Follow up 2: Given an array of integers, every element appears twice except for two. Find that two integers. Solution: First, XOR all the integers in the array we can get a result.(suppose it's c) Second, from the least significant bit to the most significant bit, find the first '1' position(suppose the position is p). Third, divided the integers in to two groups, the p position is '1' in one group, '0' in other group. Fourth, XOR all the integers in the two groups, and the results is the two integers we want.

Answer 5

I'm stealing Michael Sofaer's answer and reimplementing it in Python and C:

Python:

def singleton(array):
    return reduce(lambda x,y:x^y, array)

C:

int32_t singleton(int32_t *array, size_t length)
{
    int32_t result = 0;
    size_t i;
    for(i = 0; i < length; i++)
        result ^= array[i];
    return result;
}

Of course, the C version is limited to 32-bit integers (which can trivially be changed to 64-bit integers if you so desire). The Python version has no such limitation.

Answer 6

Here's a solution in Python that beats the Ruby one for size (and readability too, IMO):

singleton = lambda x: reduce(operator.xor, x)

Answer 7

Python 3.1 Solution:

>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>> 

• Paddy.

Answer 8

Algo 2:

1. Sort the array.
2. Now parse the array and if 2 consecutive numbers are not same we got our number.
3. This will not use extra space

Answer 9

This doesn't fit the bill for "no extra space" but it will cut the space unless the numbers are sorted in a certain way.

In Python:

arr = get_weird_array()
hash = {}

for number in arr:
   if not number in hash:
     hash[number] = 1
   else:
     del hash[number]

for key in hash:
    print key