CareerCup

example array: {1,1,2,2,3,3,4,4,5,5,5,6,6,7,7,8,8,8,8,9,9,10,10}

XOR each element with each other: all integers appearing an even amount of times will cancel each other out leaving the only element appearing an odd number of times (7 XOR 7 XOR 7 = 0 XOR 7 = 7).

1) Use XOR operator - xor each element in the array then duplicated elements will reduce each other ; time O(n), space O(1)
2) Use Set - add elements to the Set. If the set already contains given element then remove from the set. At the end set will contain only not duplicated element; time O(n), space O(n)
3) Sort array and use running counter to find not duplicated element; time O(nlogn), space O(1)

1. Do ExOr of all the elements. the result will be the output........ O(N)
2. Hashing can be used.......... O(N)
3. Sorting and iteration can be used...... O(NlogN)

import java.util.*;
import java.io.*;

//Time Complexity: O(n)

public class Gap
{

    public static void main(String args[])
    {
       int arr[] = {1,1,2,2,3,3,4,4,5,5,5,6,6,7,7,8,8,8,8,9,9,10,10};
       
       ArrayList<Integer> odd = new ArrayList<Integer>();
       
       for(int n : arr)
       {
           int result = odd.indexOf(n);
           if(result != -1)
           {
              odd.remove(result);               
           }
           else
           {
              odd.add(n);
           }           
       }
       
       System.out.println("\nNumber occuring Odd number of times: ");
       
       ListIterator<Integer> listPtr = odd.listIterator();
       
       while(listPtr.hasNext())
       {
           System.out.println(listPtr.next());
       }
    }  

}

I believe this would not be O(n) since ArrayList would search linearly for every single search. HashMap is a better option.

A : using XOR ( Code below - assuming Sorted array.. ) - O(n)
B: Use HashTable

#include <stdio.h>
#include <stdlib.h>

void printOddOccuringElements(int arr[], int length)
{
        int temp[length];
        int currentNum = arr[0];
        int XORForCurrent = currentNum;
        //Assuming Sorted
        for( int i = 1 ; i <= length ; i++) {
                if(arr[i] == currentNum){
                        XORForCurrent ^=arr[i];
                }else{
                        if (XORForCurrent != 0 ){
                                printf("OddOccurances of %d found\n", XORForCurrent);
                        }else{
                                printf("EvenOccurances of %d found\n",currentNum);
                        }
                        currentNum = arr[i];
                        XORForCurrent = currentNum;
                }
        }
}
int main(int argc , char **argv)
{
        int arr[10]= {0,0,1,1,1,2,2,2,3,3};
        printOddOccuringElements(arr, 10);
        return 0;
}

#include<iostream>
using namespace std;
int main()
{
   
              int n,a[10000],ans=0;
              scanf("%d",&n);
              
              for(int i=0;i<n;i++)
              {
                      cin>>a[i];
                      ans=ans^a[i];
                      
              }
              cout<<ans<<endl;
    return 0;
}