Find the Only Non Repeating Element Using XOR in DSA C++ - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

For each element in array

↓

Apply XOR: result = result XOR element

↓

Repeat for all elements

↓

Result holds the non-repeating element

↓

Return result

We start with zero and XOR it with every element in the array. Pairs cancel out, leaving only the unique element.

Execution Sample

DSA C++

int findUnique(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i];
    }
    return result;
}

This code finds the only element that does not repeat by XORing all elements.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State
1	Initialize result	N/A	N/A	0	result=0
2	XOR with arr[0]	2	0	2	0 ^ 2 = 2
3	XOR with arr[1]	3	2	1	2 ^ 3 = 1
4	XOR with arr[2]	2	1	3	1 ^ 2 = 3
5	XOR with arr[3]	4	3	7	3 ^ 4 = 7
6	XOR with arr[4]	3	7	4	7 ^ 3 = 4
7	XOR with arr[5]	4	4	0	4 ^ 4 = 0
8	XOR with arr[6]	5	0	5	0 ^ 5 = 5
9	End of array	N/A	5	5	Unique element found: 5

💡 All elements processed; pairs canceled out leaving unique element 5.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	0	2	1	3	7	4	0	5	5
current_element	N/A	2	3	2	4	3	4	5	N/A

Key Moments - 3 Insights

Why does XORing pairs of the same number cancel out to zero?

Because XOR of a number with itself is zero, as shown in steps 6 and 7 where 4 ^ 4 = 0 (execution_table rows 6 and 7).

Why do we start result with zero?

Zero is the identity for XOR, so XORing zero with any number returns that number, as seen in step 2 where result starts at 0 and becomes 2 after XOR.

How does the final result hold the unique element?

All repeating elements cancel out in pairs, leaving only the unique element in result, demonstrated in the final step where result is 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the result after XOR?

A 4

B 7

C 3

D 1

💡 Hint

Check the 'Result After XOR' column in row 5 of execution_table.

At which step does the result become zero again after initial changes?

A Step 7

B Step 6

C Step 4

D Step 8

💡 Hint

Look for when 'Result After XOR' is zero in execution_table rows.

If the array had no unique element, what would the final result be?

A The first element

B The last element

C Zero

D Undefined

💡 Hint

Pairs XOR to zero, so no unique element means final XOR is zero (see exit_note).

Concept Snapshot

Find unique element by XORing all array elements.
XOR pairs cancel out to zero.
Start with result = 0.
XOR result with each element.
Final result is the unique element.
Works only if exactly one element is unique.

Full Transcript

This concept finds the only non-repeating element in an array using XOR. We start with a variable result set to zero. Then, for each element in the array, we XOR it with result. Because XOR of a number with itself is zero, all repeating elements cancel out. The final value of result after processing all elements is the unique element. The code example shows a simple loop applying XOR to each element. The execution table traces each step, showing how result changes. Key moments clarify why XOR cancels pairs and why we start with zero. The visual quiz tests understanding of intermediate results and final output. This method is efficient and uses constant extra space.

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