CareerCup

Take the XOR of all the numbers -- this is the XOR of the two missing numbers. Since they differ in at least 1 bit, the XOR is nonzero in at least 1 bit. Identify one such bit position.

Now, make a second pass through the array, XORing only numbers with that bit position set to 0 and ignoring the others. You will get one of the missing numbers as a result. Make a third pass that will consider only numbers with that bit position set to 1 to find the second missing number.

It's not apparent how to generalize this idea to 3 or more missing numbers, because 3 missing numbers that are all distinct could have an XOR of 0.

I think hashes are definitely needed. Thus you find all numbers appeared once in O(n) time. Some quick example below (in Ruby):

def find_single(ar)
    num_hash = Hash.new(2)
    ar.each do |n| 
        num_hash[n] -= 1
        num_hash.delete(n) if num_hash[n] <= 0
    end
        
    return num_hash.keys
end

2 numbers with single instance:

- XOR all the numbers.
- The final hash will have 2 numbers that occur only once 
- Go through the array XOR'ing each number with final hash and check whether the  
  remaining value is present in the array (we can use hashmap to improve lookup time). 
- We have our two numbers when the value is found.

I think the same logic can be extended to solve 3, .. 100 numbers.

// only 1 number appears once and others twice

int unique_number(const vector<int>& a)
{
         int ans(0);
         for (int i=0; i < 32; i++) 
         {
                int b(0);
                for (int i=0; i < a.size(); i++)
                            b = ( b + ( a[i] & (1 << i) ? 1 : 0 ) ) %2 ; 
                if (b) ans |= (1 << i);
         }
         return ans;
}

we can do this with XOR....suppose 2 elements are present one time....lets take an example
given array is {1,3,1,2,2,5,4,5} our output will be 3 and 4

step 1: XOR all elements...we get 3(XOR)4=111(in binary)
step 2: check first one in binary of XOR from right side....in our example first LSB is one....which means...LSB of required numbers is are not same.....
step 3: divide array in two parts..first part numbers has 1 at LSB and second part number has 0 at LSB

step 4: take XOR of first part we get first number and XOR of second part give second

our example
first part: 1(001),1(001),3(011) ,5(101), 5(101) .....XOR of these give 3
secont part: 2(010),2(010),4(100) XOR of these give 4

output: 3,4....which is required

i think for number more then 2 unique numbers..suppose for 10 unique numbers we have to divide array further to get all 10 element(for further division we can use other bits of xor)

I think the idea is to use hash
if key exists then we remove it from hash else we add it to hash , as result the hash will remain just with those that are unique and is O(n)

we can do by using a set and an array, first add the elements one by one into set and into the array. If suppose any element is repeated then it will fail, when we try to add into set, then check if the same element is present in the array,if yes, then delete it from the array.

For 1 and 2 non repeating numbers cases XOR method is OK.

For 3 or more non-repeating numbers we have to use hashtable and for repetition we need to count the appearance. In final round we need to go through whole hash table and output the numbers which appeared exactly once.

Seems like hashing or XORing are the two answers everyone here agrees on. I will go with the hashing since this kind of interview problem is usually given to test your knowledge of data structures (i.e. which one would work best and how)

So let's do this one in java real quick, using the obvious method, usually used for questions that ask for a fast way to find if a string contains duplicates (the principle can be applied to this without much adjustment).

public int[] find_unique(int[] a){
   HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
   for(int i = 0; i < a.length; i++){
      if(map.containsKey(a[i]) == true) map.put(a[i], map.get(a[i]) + 1);
      else map.put(a[i], 1);
   }
   ArrayList<Integer> uniques = new ArrayList<Integer>();
   for(int i = 0; i < a.length; i++){
      if(map.get(a[i]) == 1) uniques.add(a[i]);
   }
   return uniques.toArray();
}

Side note: not sure if the toArray I used would work in this case, whatever, you get the idea.

How it works: The method runs through and assesses the total count of all values in the original array. That takes O(n) time assuming the hashing function is decent. Then the method runs through again, after creating an initially empty arrayList, and any entry in a that has a stored value of 1 (meaning it was only seen once) is appended to the list. the list is then returned. The second half takes O(n) time, again assuming we have a decent hashing function.

This isn't as elegant as using logical operations, but you can get some brownie points in the interview if you mention that the runtime could potentially be O(n^2) if the hashing function is bad (i.e. tons of collisions).

void findUniqueNumbers(int arg[], int length)
{
	map<int, int> numbers;
	map<int, int>::iterator it; 
	
	for(int i = 0; i < length; ++i)
	{
		++numbers[arg[i]];
	}
	for(it = numbers.begin(); it != numbers.end(); ++it)
	{
		if(it->second == 1)
			cout<<"unique number "<<it->first<<endl;
		
	}
	
}

Would it be wrong to use a hashset? Traversing through the array once, adding to the hashset when it doesn't contain the value and removing if it does contain it. Leaving you with a set at the end with only values that appeared once.

how about writing a simple loop. O(n^2)

void finder(int a[],int size){
	int flag=0;
	for(int i=0;i<size;i++){
		flag=0;
		for(int j=0;j<size;j++){
			if(i==j)
				j++;
			if(a[i]==a[j]){
				flag=1;
				break;
			}

		}
		if(flag==0)
			cout<<a[i]<<"  is unique"<<endl;
	}

}

If there's more than one number appearing once, i think we need to use hashing.

1. Sort all the elements. Duplicate elements will appear together.
2. Iterate the sorted elements to find out whether an elements is unique by performing equality test with previous one.