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

↓

After all elements processed

↓

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 result = 0;
foreach (int num in arr) {
  result ^= num;
}
return result;

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

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Explanation
1	Initialize result	N/A	N/A	0	Start with result = 0
2	XOR with element	2	0	2	0 XOR 2 = 2
3	XOR with element	3	2	1	2 XOR 3 = 1
4	XOR with element	2	1	3	1 XOR 2 = 3
5	XOR with element	4	3	7	3 XOR 4 = 7
6	XOR with element	3	7	4	7 XOR 3 = 4
7	XOR with element	4	4	0	4 XOR 4 = 0
8	XOR with element	5	0	5	0 XOR 5 = 5
9	End	N/A	5	5	Result is 5, the non-repeating element

💡 All elements processed; pairs canceled out leaving the 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	N/A	2	1	3	7	4	0	5	5

Key Moments - 3 Insights

Why do pairs of repeating elements cancel out when XORed?

Because XOR of a number with itself is 0, as shown in step 7 where 4 XOR 4 = 0, removing duplicates from the result.

Why do we start with result = 0?

XOR with 0 leaves the number unchanged, so starting with 0 allows the first element to set the initial result, as seen in step 2.

What if the array has only one element?

The loop XORs 0 with that element, so the result is that element itself, correctly identifying it as unique.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of result after processing the third element?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'Result After XOR' column at Step 3 in the execution table.

At which step does the result become zero during the XOR process?

A Step 7

B Step 5

C Step 6

D Step 8

💡 Hint

Look for 'Result After XOR' equal to 0 in the execution table.

If the array had no repeating elements, what would the final result be?

A The first element

B 0

C The XOR of all elements

D Undefined

💡 Hint

Consider how XOR accumulates all elements when none cancel out, as shown in the variable tracker.

Concept Snapshot

Find unique element by XORing all array elements.
Pairs cancel out because x XOR x = 0.
Start with result = 0.
Final result is the non-repeating element.
Works in O(n) time and O(1) space.

Full Transcript

This concept uses XOR to find the only non-repeating element in an array. We start with a result variable set to zero. Then, for each element in the array, we XOR it with the result. Because XOR of a number with itself is zero, pairs of repeating elements cancel out. After processing all elements, the result holds the unique element. For example, with the array [2,3,2,4,3,4,5], the result after each XOR step changes until finally it is 5, the only non-repeating element. 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 the number itself

B. It causes an error

C. It returns 1

D. It returns 0

Solution

1. Step 1: Understand XOR behavior on identical bits

   XOR returns 0 when both bits are the same (0 XOR 0 = 0, 1 XOR 1 = 0).

2. Step 2: Apply XOR on identical numbers

   Since all bits are identical, XOR of a number with itself results in 0.

3. Final Answer:

   It returns 0 -> Option D

4. Quick Check:

   5 XOR 5 = 0 [OK]

Hint: XOR of same numbers always zeroes out [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR or AND
• Assuming XOR causes errors with identical inputs

2. Which of the following is the correct syntax to initialize an integer variable named result to zero in C#?

easy

A. int result => 0;

B. int result == 0;

C. int result = 0;

D. int result := 0;

Solution

1. Step 1: Recall C# variable initialization syntax

   In C#, variables are initialized using single equals sign (=) for assignment.

2. Step 2: Check each option

   int result = 0; uses correct syntax: int result = 0;. Others use invalid operators.

3. Final Answer:

   int result = 0; -> Option C

4. Quick Check:

   Correct assignment uses = in C# [OK]

Hint: Use single = for assignment in C# [OK]

Common Mistakes:

• Using double equals (==) for assignment
• Using := or => which are invalid here
• Missing semicolon at the end

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

int[] arr = {2, 3, 2, 4, 3};
int result = 0;
foreach (int num in arr) {
    result ^= num;
}
Console.WriteLine(result);

medium

A. 4

B. 3

C. 2

D. 0

Solution

1. Step 1: XOR all elements in the array

   Start with result = 0. XOR with 2 -> 0^2=2, then 3 -> 2^3=1, then 2 -> 1^2=3, then 4 -> 3^4=7, then 3 -> 7^3=4.

2. Step 2: Final XOR result is the non-repeating element

   The final result after XORing all elements is 4, which is the only non-repeating number.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Only 4 appears once, XOR result = 4 [OK]

Hint: XOR all numbers; duplicates cancel out [OK]

Common Mistakes:

• Not XORing all elements correctly
• Confusing XOR with addition
• Assuming first unique number is output

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

int[] arr = {1, 2, 1, 3, 2};
int result;
foreach (int num in arr) {
    result ^= num;
}
Console.WriteLine(result);

medium

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

B. Using '^=' operator is incorrect for XOR in C#

C. Array syntax is invalid

D. Console.WriteLine cannot print integers

Solution

1. Step 1: Check variable initialization

   The variable 'result' is declared but not initialized before using '^=' operator, which causes a compile-time error.

2. Step 2: Correct initialization needed

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

3. Final Answer:

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

4. Quick Check:

   Uninitialized variables cause errors in C# [OK]

Hint: Always initialize variables before use [OK]

Common Mistakes:

• Forgetting to initialize variables
• Misunderstanding '^=' operator usage
• Assuming Console.WriteLine can't print ints

5. Given an array where every element appears twice except one element which appears once, how would you modify the XOR approach to find the unique element if the array is very large and you want to optimize memory usage?

hard

A. Sort the array first then scan for unique element

B. Use XOR in a single pass without extra memory

C. Use a dictionary to count occurrences

D. Copy array to a new list and remove duplicates

Solution

1. Step 1: Understand XOR single pass advantage

   XOR operation can be done in one pass over the array without extra memory, as duplicates cancel out.

2. Step 2: Avoid extra memory by not using sorting or dictionaries

   Sorting or dictionaries use extra memory or time, which is inefficient for large arrays.

3. Final Answer:

   Use XOR in a single pass without extra memory -> Option B

4. Quick Check:

   XOR single pass = memory efficient [OK]

Hint: XOR once over array; no extra memory needed [OK]

Common Mistakes:

• Using extra data structures unnecessarily
• Sorting which costs extra time and memory
• Copying arrays wastes memory