Codefest

Problem 2: Odd one out

In the given list of integers, every integer is repeated even number of times except one of them. Find the integer which is repeated odd number of times.

Input:

First line contains number of test cases T.
Then T test cases follow. First line for each test case contains number of elements N in the list and in next line, there are N integers separated by a single white-space character.

Output:

The output file contains T lines.
For each test case, print the integer which is repeated odd number of times.

Constraints:

T<30
0<N<21
The list contains 32-bit integers.

Sample input:

3

5

1 2 1 2 3

9

4 5 4 7 5 4 5 4 5

3

9 6 6

Sample Output:

3

7

9

Score:

B: Number of square brackets which are [ and ]
S: Number of * and /
C: Total number of non-whitespace characters

T=10000/(C + 400*B + 100*S)

Solution:

A brute-force approach for this problem is to maintain an array of input integers and we count number of occurences of all unique integers in the array.
But this method does not score good as use of array is restricted through pointers and square brackets.

There is an alternate solution to this problem by bitwise operator XOR(^). We know:
1. A^A = 0
2. A^0 = A

When we take XOR of all numbers, the numbers repeating even number of times will results to 0 and the XOR of 0 with the number repeating odd number of times will give the number itself.
Check the Best Solutions