Chef and Dolls

In this problem, Chef loves pairs of dolls. Every doll type should appear an even number of times (in pairs).

But Chef notices that there are an odd number of dolls in total, which means exactly one doll type is missing its pair.

Your task: Find the doll type that does not have a pair.

1. Problem Statement (Simplified)

You are given multiple test cases.
For each test case:

• You are given an integer N (odd), the total number of dolls currently present.

• Then you are given N integers where each integer represents the type of a doll.

• All doll types appear an even number of times except one type, which appears an odd number of times.

You must print the type of the doll that does not have a pair for each test case.

Input Format:

• First line: Integer T — number of test cases.

• For each test case:

• First line: Integer N — number of dolls (odd number).

• Next N lines: Each line contains an integer — the type of a doll.

Output Format:

• For each test case, print a single integer: the type of the doll that doesn’t have a pair.

Constraints:

• 1 <= T <= 10

• 1 <= N <= 105

• 0 <= type <= 105

Total input size can go up to about 106 integers across test cases, so the solution must be efficient.

Sample 1:

Input:

1

3

1

2

1

Output: 2

Explanation:

Dolls: [1, 2, 1]

• Type 1 appears twice → has a pair

• Type 2 appears once → does not have a pair

So the missing doll type is 2.

Sample 2:

Input:

1

5

1

1

2

2

3

Output: 3

Explanation:

Dolls: [1, 1, 2, 2, 3]

• Type 1 → 2 times (paired)

• Type 2 → 2 times (paired)

• Type 3 → 1 time (unpaired)

Unpaired doll type = 3.

2. Approaches Overview

We will discuss two approaches:

1. Basic Approach: Using Frequency Map (Hash Map)

2. Optimized Approach: Using Bitwise XOR

2.1. Basic Approach – Using Frequency Map:

Idea:

Count how many times each doll type appears using a map / dictionary.
The doll type that has an odd count is the answer.

Algorithm:

For each test case:

1. Read integer N.

2. Initialize an empty map freq.

3. Repeat N times:

• Read doll type x.

• Increment freq[x] by 1.

4. Iterate over the keys of freq:

• Find the key whose value is odd (freq[key] % 2 != 0).

• Print that key.

Time & Space Complexity:

• Time: O(N) per test case (counting + scanning map).

• Space: O(K) where K is the number of distinct doll types.

This passes easily, but we can do better in terms of space and code simplicity.

2.2. Optimized Approach – Using Bitwise XOR:

Key Observation:

Use the properties of XOR:

• a ⊕ a = 0

• a ⊕ 0 = a

• XOR is commutative and associative:

• a ⊕ b = b ⊕ a

• (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

If every type except one appears exactly twice, then if we XOR all the doll types:

• All paired doll types cancel out to 0.

• Only the type that appears once (unpaired) remains.

So:

• answer = x1​ ⊕ x2 ​⊕ ⋯ ⊕ xN​

Algorithm:

For each test case:

1. Read integer N.

2. Initialize result = 0.

3. Repeat N times:

• Read doll type x.

• Do result = result XOR x.

4. After the loop, result is the type that does not have a pair.

5. Print result.

Example:

Dolls: [1, 2, 1]
Compute:

• result = 0 ^ 1 = 1

• result = 1 ^ 2 = 3

• result = 3 ^ 1 = 2

Answer = 2

Time & Space Complexity:

• Time: O(N) per test case

• Space: O(1) extra

This is the best approach for this problem and is the expected solution in competitive programming.

Pseudocode (Optimized XOR Approach):

3. Java code:

4. C code:

5. C++ code:

6. Python code:

7. JavaScript code: