CareerCup

Assume that X repeats once, Y repeats 3 times and each of the rest repeats twice.

Let S = XOR of all elements in the array, thus S = X XOR Y

Since X != Y, S != 0. Hence there exists some integer i such that the i-th of S is 1, which indicates that the i-th bit of X != the i-th bit of Y.

Let S1 = XOR sum of all elements in the array whose the i-th bit equal to 0.
Let S2 = XOR sum of all elements in the array whose the i-th bit equal to 1.

{S1, S2} = {X, Y} are two numbers that we're looking for.

Complexity: O(m+n+m) = O(m+n) where m is the size of the array, n is the bit-length of elements in the array, which is small. So basically, it's O(m).

This is a duplicate question and was already discussed b4. Plz search if a question already exist before posting it!

for (int i = 0; i < len; i++)
{
SecIndex = 0;
for (int j = i + 1; j < len; j++)
{
if ((input[i] ^ input[j]) == 0)
{
if (SecIndex == 0)
SecIndex = j;
else
return input[i];
}
}
}

For solving the above algorithm we have to find the element with ocurrance 1 for this we have to add the last bit of every integer in the array and then, we will check if the & operation with the last bit of the integer is 1 then we will increment the sum and then at every step we will check if the sum of all integers is not divisible with 3 if yes then that number will be non repeating in the array.

Implementation:

{int findnonrepeating(int n){
int sum;
int result = 0;
for(int i = 0; i < 32; i++){
	sum = 0;
	int x = (1<<i);
	for(int j = 0; j <n; j++){
		if(arr[j]&x)
			sum++;
	}
	if(sum%3)
		result = result | x;
}
return result;

XOR all the numbers in the array o(n). This will result in XOR of the number repeated once and thrice. Because the XOR of numbers repeated twice would have cancelled each other and XOR of number thats repeated 3 times would result in number itself.
Now XOR the obtained result with each element in the list again. if the result is zero search the array to find if that no is the one that appears thrice or once.
Overall complexity : O(n)