CareerCup

It can be done without extra storage given the data has some bounds. Generally, if you have n elements and you are guaranteed that the elements are between 0 to n-1, we can use the value of the element itself as an "index" within the array and change the data to mark the item as read. For example, if a[i] =3, you can go to third index and multiply the value by -1 (a[3] * -1). But this requires the data to be bounded

sort

Having made sure that sorting is OK, please see the implementation at the link below:
codepad.org/niDD5OZ1

O(n) time O(1) Space

1. Find max and min
2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]

Each time a element is found sign of location corresponding to that
(mapped to a[i]-min) changes sign. So same sign after this traversal means
even number of occurrences, different sign means odd no. of occurrences

3.Finally traverse the array from i =0 to i = max-min
and look for -ve element at location 'j'.
4. Return j+min

This algorithm will work only if all elements are of same sign initially

What is correct solution for this problem?

#include <math.h>
void main()
{
int a[] = {3,3,5,5,5,7,7,8,8,8,9,9,3};

for(int i = 0; i<13; i++)
{

if(a[abs(a[i])] > 0)
{
a[abs(a[i])] = -a[abs(a[i])];
}
else
{
a[abs(a[i])] = -a[abs(a[i])];
}
}

for(int i =0; i<13; i++)
{
if(a[abs(a[i])] > 0)
{
printf("\n even time %d ", abs(a[i]));
}
/* else
{
printf("\n odd time %d ", abs(a[i]));
}*/
}
}

What if I will change the array to int a[] = {13,3,5,5,5,7,7,8,8,8,9,9,3}
made the first element of array greater than the length of the array

Assuming the array can be sorted using standard C/C++ library functions here is the code to count the even number of occurring elements in the given array. It is better to ask the interviewer that the array can be sorted as suggested by some one in this thread.

void CountEvenOccurences(int *array,int length)
{
	int prev_key = array[0];
	int num_count = 1;
	for (int i = 1; i < length; i++) {
		int curr_key = array[i];
		if (curr_key == prev_key) {
			++num_count;
			continue;
		}
		if ( (num_count %2) == 0 ) {
			printf("Element %d occurs %d times.\n",prev_key,num_count);
		}
		prev_key = curr_key;
		num_count = 1;
	}
}

public class EvenlyRepeated {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		System.out.println("Even repetation xor is " + (3 ^ 3 ^ 3 ^ 3));
		System.out.println("Odd repetation xor is " +  (2 ^ 2 ^ 2));
		
		int[] values = { 1, 2, 3, 4, 1, 2, 3, 1, 2, 1 };
		for (int i = 0; i < values.length; i++) {
			int result = values[i];
			for (int j = 0; j < values.length; j++) {
				if (i != j && values[i] == values [j]) {
					result = result ^ values[j];
				}
			}
			if (0 == result) {
				System.out.println(values[i]);
			}
		}
	}

}

This works but prints repeated numbers every time it appears in array. This can be fixed by sorting array and then breaking loop on next number.

//O(n log n) solution
	public static void printOutEvenRepeats(int[] A) {
		Arrays.sort(A); //O(n log n)
		int currentNum = A[0];
		int numSeen = 0;
		for (int i = 0; i < A.length; i++) {    // O(n) in worst case
//			We see the same number
			if (A[i]==currentNum) {
				numSeen++;
				if (i==A.length-1) {
					if (numSeen != 0 && numSeen % 2 == 0)
						System.out.println("We saw  " + currentNum + " an even number of times.");
				}
			}
//			The value at this array index is a different number.  Reset numSeen and the currentNum
			else {
				if (numSeen != 0 && numSeen % 2 == 0)
					System.out.println("We saw " + currentNum + " an even number of times.");
				numSeen = 1;
				currentNum = A[i];
			}
		}

}