CareerCup

We could simply sort the numbers O(n*log(n)) and do a scan+count on the fly. Stop when we hit the count is even and found a non-matching number.

I guess, the intent is to get algorithm with time complexity O(n) and space complexity O(constant).

best solution on the page

import java.util.Hashtable;
import java.util.Set;
import java.util.Iterator;


public class FindOddNumber {

public static void main(String args[]){

int arr[]={1,2,4,3,4,3,3};

Hashtable table=new Hashtable();
int result=0;
for (int i=0;i<arr.length;i++){
result=result^arr[i];
if(table.containsKey(arr[i]))
continue;
else
table.put(arr[i],true);
}

Set set = table.keySet();
Iterator it = (Iterator) set.iterator();

int a;
while(it.hasNext()){
a=((Integer)it.next()).intValue();
result=result^a;
}

for(int i=0;i<arr.length;i++)
result=result^arr[i];

System.out.println(result);
}
}

the for loop towards the end is not der ...plz remove it.... my mistake.....we hav already XORed all elements in the array above , no need to do it again.

wrong solution , it is correct for only ur input

consider this
{1,2,4,3,4,3,3,5}

unique elements are 1,2,3,4,5
answer should be 4
but with ur solution it is 1 (the XOR of 1,2,3,4,5 is 1)

i am gettin correct solution ...... juss remove d last for loop in my code

If it helps, here is why the code works.

If we append all unique elements to the collection, then the collection would have all numbers repeated even number of times except one. In this situation, XOR of all values would yield the only element that occurred odd number of times.

Here the code is first getting XOR of all array and then the XOR values is continued (see result is not reset to zero) to the unique value set.

Hence, the code works.

Thanks,
Laxmi

As a pseudocode:

1. create a HashTable and all elements to it // This collection will have jus one copy all elements in the input array
2. also XOR all elements in the array into a variable "result".
// result will have the XOR of numbers repeated odd number of times.
3. Now, while iterating the collection, XOR those elements with the "result"
4. At the end of this XORing Loop, we will have "result" having the even no. of elements

Good approach Puneet and nice explanation Laxmi

Very Smart Puneet .. Basically you are just reversing the question to all even and one odd. But wont the computation time/space increase with finding unique elements in array ?

Good approach.. Somewhat simplified implementation.

public static int getEvenRepeatedNum(int a[]){
		int result=0,i;
		
		Hashtable<Integer,Integer> table = new Hashtable<Integer, Integer>();
		
		for (i=0;i<a.length;++i){
			result^=a[i];
			table.put(a[i], 1);
		}
		Enumeration<Integer> e = table.keys();
		 
	    //iterate through Hashtable keys 
	    while(e.hasMoreElements())
	      result^=e.nextElement();
	  
		return result; 
	}

int a[] = {3, 4, 5, 4, 5};
int result = a[0];
for (int i = 1; i < 5; ++i)
{
result ^= a[i];
}
cout << result << endl;

return 0;

sort and count nlogn and no space complexity

@ Anonymous

at least check your approach with 1 or 2 examples before posting here.

Totally absurd and wrong.