Find the Only Non Repeating Element Using XOR in DSA C#

Mental Model

XORing a number with itself cancels out to zero, so XORing all numbers leaves only the unique one.

Analogy: Imagine you have pairs of socks in a drawer. If you take out all socks and pair them up, only the single unmatched sock remains alone.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 -> 2
          2 ⊕ 3 -> 1
          1 ⊕ 2 -> 3
          3 ⊕ 4 -> 7
          7 ⊕ 3 -> 4
Result: 4 (only non-repeating)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result with first XOR to start cancelling pairs

Step 2: XOR result with next element 3

result = 2 ⊕ 3 = 1

Why: XOR with 3 updates result to reflect unique so far

Step 3: XOR result with next element 2

result = 1 ⊕ 2 = 3

Why: XOR with 2 cancels previous 2, leaving unique influence

Step 4: XOR result with next element 4

result = 3 ⊕ 4 = 7

Why: XOR with 4 adds new unique number influence

Step 5: XOR result with last element 3

result = 7 ⊕ 3 = 4

Why: XOR with 3 cancels previous 3, leaving only 4

Result:

Final result = 4 (only non-repeating element)

Annotated Code

DSA C#

using System;

class Program
{
    // Function to find the only non-repeating element using XOR
    static int FindUnique(int[] arr)
    {
        int result = 0;
        foreach (int num in arr)
        {
            result ^= num; // XOR accumulates unique number
        }
        return result;
    }

    static void Main()
    {
        int[] arr = {2, 3, 2, 4, 3};
        int unique = FindUnique(arr);
        Console.WriteLine(unique);
    }
}

result ^= num; // XOR accumulates unique number

XOR current number with result to cancel duplicates and keep unique

Output

4

Complexity Analysis

Time: O(n) because we traverse all n elements once

Space: O(1) because we use only one variable to store XOR result

vs Alternative: Better than using a hash map which uses O(n) space; XOR uses constant space and linear time

Edge Cases

Array with only one element

Returns that element as unique

DSA C#

result ^= num; // XOR accumulates unique number

Array where all elements repeat except one

Correctly returns the single non-repeating element

DSA C#

result ^= num; // XOR accumulates unique number

Empty array

Returns 0 as no elements to XOR

DSA C#

int result = 0;

When to Use This Pattern

When you see a problem asking for the single unique element among duplicates, reach for the XOR pattern because it cancels pairs efficiently.

Common Mistakes

Mistake: Starting XOR result with first array element instead of 0
Fix: Initialize result with 0 to handle empty arrays and simplify logic

Mistake: Using addition or subtraction instead of XOR
Fix: Use XOR operator (^) because it cancels duplicates correctly

Summary

Finds the only non-repeating element in an array where all others repeat.

Use when you need to identify a unique number among pairs efficiently.

XORing duplicates cancels them out, leaving only the unique number.

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