Find the Only Non Repeating Element Using XOR in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR to find non-repeating element

What is the output of this C++ code that uses XOR to find the only non-repeating element in the array?

DSA C++

int arr[] = {2, 3, 5, 4, 5, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
int result = 0;
for(int i = 0; i < n; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

A 4

B 3

C 5

D 2

💡 Hint

XOR of a number with itself is 0, and XOR with 0 is the number itself.

All repeating elements cancel out because XOR of a number with itself is zero. Only the non-repeating element remains.

❓ Predict Output

intermediate

Result of XOR with multiple repeating pairs

What will be printed by this code snippet that finds the only non-repeating element using XOR?

DSA C++

int arr[] = {10, 14, 10, 14, 20};
int n = sizeof(arr)/sizeof(arr[0]);
int res = 0;
for(int i = 0; i < n; i++) {
    res ^= arr[i];
}
std::cout << res << std::endl;

A 14

B 10

C 20

D 0

💡 Hint

Pairs cancel out, leaving the unique number.

10 and 14 appear twice and cancel out, leaving 20 as the unique element.

🔧 Debug

advanced

Identify the error in XOR implementation

What error does this code produce when trying to find the only non-repeating element using XOR?

DSA C++

int arr[] = {1, 2, 1, 3, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int result = 0;
for(int i = 0; i < n; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

A Undefined behavior due to uninitialized variable 'result'

B Output is 3

C Compilation error: missing semicolon

D Runtime error: segmentation fault

💡 Hint

Check variable initialization before using XOR.

Variable 'result' is used without initialization, causing undefined behavior.

❓ Predict Output

advanced

Output of XOR with negative numbers

What is the output of this code that finds the only non-repeating element using XOR with negative numbers?

DSA C++

int arr[] = {-1, -2, -1, -3, -2};
int n = sizeof(arr)/sizeof(arr[0]);
int result = 0;
for(int i = 0; i < n; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

A 3

B -3

C 0

D -1

💡 Hint

XOR works the same with negative numbers as with positive.

All repeating negative numbers cancel out, leaving -3 as the unique element.

🧠 Conceptual

expert

Why XOR finds the only non-repeating element?

Why does XOR operation help find the only non-repeating element in an array where every other element repeats exactly twice?

A Because XOR of a number with itself is zero and XOR with zero is the number itself, so pairs cancel out leaving the unique number.

B Because XOR adds all numbers together and the sum is the unique number.

C Because XOR sorts the array and the unique number is at the start.

D Because XOR multiplies all numbers and the product is the unique number.

💡 Hint

Think about how XOR behaves with pairs of identical numbers.

XOR cancels out pairs because n ^ n = 0, and 0 ^ n = n, so only the unique element remains after XORing all elements.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns 0

B. It returns the number itself

C. It returns 1

D. It returns the sum of the numbers

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself always results in 0 because bits cancel out.

2. Step 2: Apply XOR to example

   For example, 5 XOR 5 = 0.

3. Final Answer:

   It returns 0 -> Option A

4. Quick Check:

   X XOR X = 0 [OK]

Hint: XOR of same numbers is always zero [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR or AND
• Assuming XOR returns 1 for identical numbers

2. Which of the following is the correct syntax to find the XOR of two integers a and b in C++?

easy

A. int result = a && b;

B. int result = a ^ b;

C. int result = a | b;

D. int result = a & b;

Solution

1. Step 1: Identify XOR operator in C++

   The XOR operator in C++ is the caret symbol (^).

2. Step 2: Check syntax correctness

   Using int result = a ^ b; correctly computes XOR of a and b.

3. Final Answer:

   int result = a ^ b; -> Option B

4. Quick Check:

   Use ^ for XOR in C++ [OK]

Hint: Use ^ symbol for XOR in C++ [OK]

Common Mistakes:

• Using && instead of ^ for XOR
• Using | or & which are OR and AND
• Missing semicolon at end

3. What is the output of the following C++ code?

int arr[] = {2, 3, 5, 4, 5, 3, 4};
int result = 0;
for(int i = 0; i < 7; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

medium

A. 2

B. 0

C. 5

D. 4

Solution

1. Step 1: XOR all elements in the array

   Perform XOR stepwise: 0^2=2, 2^3=1, 1^5=4, 4^4=0, 0^5=5, 5^3=6, 6^4=2.

2. Step 2: Identify the non-repeating element

   All repeating elements cancel out, leaving 2 as the only non-repeating element.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Only non-repeating element = 2 [OK]

Hint: XOR all elements; result is unique number [OK]

Common Mistakes:

• Not XORing all elements correctly
• Confusing output with a repeating element
• Assuming sum instead of XOR

4. Identify the error in the following code snippet that tries to find the only non-repeating element using XOR:

int arr[] = {1, 2, 1, 3, 2};
int result;
for(int i = 0; i < 5; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

medium

A. XOR operator '^' is used incorrectly; should be '&&'

B. Loop runs one extra iteration causing out-of-bounds access

C. Variable 'result' is not initialized before XOR operation

D. Array size is incorrect causing runtime error

Solution

1. Step 1: Check variable initialization

   The variable 'result' is declared but not initialized, so XOR with garbage value leads to wrong result.

2. Step 2: Correct initialization

   Initialize 'result' to 0 before the loop to correctly accumulate XOR.

3. Final Answer:

   Variable 'result' is not initialized before XOR operation -> Option C

4. Quick Check:

   Initialize XOR accumulator to 0 [OK]

Hint: Always initialize XOR accumulator to 0 [OK]

Common Mistakes:

• Not initializing XOR variable
• Using wrong operator instead of ^
• Incorrect loop bounds

5. Given an array where every element appears twice except one element which appears once, how can you find the unique element efficiently using XOR? Choose the best approach.

hard

A. Add all elements and subtract twice the sum of unique elements

B. Sort the array and check neighbors for unique element

C. Use a hash map to count occurrences and find the unique element

D. Initialize a variable to 0 and XOR it with every element in the array once

Solution

1. Step 1: Use XOR properties for unique element

   XORing all elements cancels out duplicates because X XOR X = 0, leaving only the unique element.

2. Step 2: Implement efficient XOR approach

   Initialize a variable to 0 and XOR it with each element in one pass for O(n) time and O(1) space.

3. Final Answer:

   Initialize a variable to 0 and XOR it with every element in the array once -> Option D

4. Quick Check:

   Single pass XOR finds unique element efficiently [OK]

Hint: XOR all elements once; duplicates cancel out [OK]

Common Mistakes:

• Using sorting which is slower
• Using extra space with hash maps
• Incorrect arithmetic approach