CareerCup

If space complexity is not an issue, why not store the occurrence frequency in an array at the index matching the number we are processing. Thats O(n). Next in another parse, print out the numbers that have even frequencies. Thats the second O(n) operation.

in first iteration count the frequency and store in a hash.
print the value from hash where frequency is even.

This is order n solution

{

private static Set<Integer> getEvenFrequencyNumber(int[] arr) {
		// TODO Auto-generated method stub
		HashMap<Integer, Boolean> hashMap = new HashMap<>();
		for(int a : arr){
			Boolean x = hashMap.get(a);
			if(x == null)
				hashMap.put(a, false);
			else
				hashMap.put(a, !x);
		}
	 Set<Integer> ar = hashMap.keySet();
	 
	 Iterator<Integer> iterate = ar.iterator();
	 while(iterate.hasNext()){
		 if(!hashMap.get(iterate.next()))
		 	 iterate.remove();
	
	 }
	 System.out.println(ar);
	 	return ar;
	}

}

/* simple hashing and uses counting sort */
#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int main()
{
int i;
int a[] = {3, 4, 3, 4, 3};
static int count[SIZE]; /* static is just for zeroing */

/* find out the frequency of the elements and store in it's
respective indexes such as if the number is 4 it will go
to 4 index and so on and once this is done we will have all
the frequency of the numbers in it's corresponding index stored*/
for(i = 0; i < SIZE;i++)
count[a[i]]++;

for(i = 0; i < SIZE;i++)
printf("%d\n", count[i]);

printf("\n");

for(i = 0; i < SIZE;i++) {
if(count[i] && count[i]%2 == 0)
printf("%d\n", i);
}
return 0;
}

In Java: Use a hashset, traverse the array, if we can find it, remove it, otherwise add it to the set, then print all numbers in the set.

get the sorted array a[]={1,1,2,2,3,4,4,4};
int freq = 0;
for(i=0; i<size-1; i++)
{
	if(a[i]==a[i+1])
		freq++;
	else if(freq>1 && (freq&1 == 1) // more then once then only frequency is taken
		printf("%d\t", freq);freq=0;

}

I doubt if HASH table will work or not. It works only if the hash function is so good that there will be no collision for any number.

The safe way is to sort first then count the frequency. If use quicksort, average O(nlog(n)) + O(n), sorting plus traverse.

what if we assign a unique prime number to every unique integer in the array and store that in a table

for eg. arr[] = {2,3,4,5,4,6,9};
2 == 11,
3 == 13,
4 == 17,
5 == 19,
6 == 23,
9 == 29;

initialize mul ==1;
for each i = 1 to N
divide mul by a[i];
if divisible, then mul = mul/a[i];
else mul = mul*a[i];

finally, traverse from j = 1 to N to check if
a[j] divides mul, then it is odd frequency else if it does not, then even frequency.

#include<stdio.h>
#include<conio.h>
int main()
{
	int a[20],n;
	printf("Enter your size of array\n");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(int j=0;j<n;j++)
	{
		int c=1;
		if(a[j]==-1)
			j++;
		for(int k=j+1;k<n;k++)
		{
			if(a[j]==a[k])
			{
				c++;
				a[k]=-1;
			}
			
		}
		if(c%2==0)
			printf("%d",a[j]);
	}
return 0;
}