CareerCup

xor the entire array elements..the result is the req ans.

In (c++ like) pseudocode.

hash_map<int,int> num2count;
  for (int i=0 ; i< array_size; ++i) {
    iterator itr - num2count.find(array[i])
    if (itr !=num2count.end())
        num2count.erase(itr); //This number occurred twice
    else 
        num2count[array[i]]=1;
  }
  return num2count.begin()->first;

If B[] is the given array, create an array Arr[] of size 10 which holds zeros (so the array indexes will be 0,1,2..9).

for (i=0;i<len(B);i++)
{
  Arr[B[i]] += 1;
}

Now B[i] should have 2's for all the duplicate elements and 1 for the lone one. Can use hashtable too.

xor the entire array elements..is the best one

if 3 duplicates or more and space is a constraint(no hastable and extra arrays) , then sort the elements may be quick sort and then have two pointers and keep incrementing the second ptr when repeats and then update first=second.

curr
next=current+1
while(1){
{
if curr!=next
return current
break

while(curr==next)
next=next+1

curr=next
next=curent+1
continue;
}

What you mean by XOR entire array element ? If you are going to be taking element one by one. THen it would be O(N^2)

Even I am not sure what do you mean by XORing the entire array, do you mean XOR each element with every other? Because if A[] is an array then A^A does not make sense to me because A is simply a pointer

void dupl(int * arr,int n){
int xor=arr[0];
for(i = 1; i < n; i++)
xor ^= arr[i];
cout<<xor;//The result
}

public class FindUnique{

public static void main(String[] args){
Integer[] ar = new Integer[]{1,8,5,8,1,3,5};
List<Integer> list = Arrays.asList(ar);
for(Integer i: list){
int frequency = Collections.frequency(list, i);
if(frequency == 1){
System.out.println(i + " occurs only once");
break;
}
}
}
}

MS and standard of ms question ?

XORing?? for one, I cant think of a way to implement it.. and two.. xoring every element woth the remaining wall give a O(n^2) time complexity..

I guess Hash map will give the best time complexity..O(n).. although there may be a better method to improve on space complexity..

Hey guys, the XORing works as O(n).. say the list is 1,2,3,4,1,2,3. Suppose we start with k=0 and xor every term with k in sequence (n terms).. we remain with 4. This is because Xoring twice with the same number gives back the original number. Hence at the end we are left with the term that is not repeated. Heres the program.

#include<stdio.h>
#include<conio.h>

void main()
{
 int list[7]={1,2,3,4,1,3,2};
 int k=0,i;

 for(i=0;i<7;i++)
 {
   k=k^list[i];
 }
 printf("Number with no duplicate: %d",k);
 getch();
}

//OUTPUT: Number with no duplicate: 4