Two Non Repeating Elements in Array Using XOR in DSA C#

Mental Model

Use XOR to cancel out pairs and find two unique numbers by splitting based on a differing bit.

Analogy: Imagine you have pairs of socks mixed in a drawer except two socks that don't have a pair. By looking at a specific color stripe that only one of the unique socks has, you separate the socks into two piles and find each unique sock easily.

Array: [2, 3, 7, 9, 2, 3]
Pairs cancel out -> only 7 and 9 remain unique
XOR all: 2⊕3⊕7⊕9⊕2⊕3 = 7⊕9
Split by rightmost set bit of XOR result:
Group 1 (bit set): 7 -> [7]
Group 2 (bit not set): 9 -> [9]

Dry Run Walkthrough

Input: array: [2, 3, 7, 9, 2, 3]

Goal: Find the two numbers that appear only once (7 and 9) using XOR operations

Step 1: XOR all elements to get xor_all = 7⊕9

xor_all = 2⊕3⊕7⊕9⊕2⊕3 = 14 (binary 1110)

Why: XOR cancels pairs, leaving XOR of two unique numbers

Step 2: Find rightmost set bit in xor_all (14) to separate groups

rightmost set bit mask = 2 (binary 0010)

Why: This bit differs between the two unique numbers

Step 3: Divide array into two groups based on this bit and XOR each group

Group 1 (bit set): 3, 7, 3 -> XOR = 7
Group 2 (bit not set): 2, 9, 2 -> XOR = 9

Why: Pairs cancel in each group, leaving one unique number per group

Step 4: XOR group 1 elements to find first unique number

XOR(3, 7, 3) = 7

Why: Pairs cancel out, leaving the unique number 7

Step 5: XOR group 2 elements to find second unique number

XOR(2, 9, 2) = 9

Why: The unique number 9

Result:

7 -> 9

Annotated Code

DSA C#

using System;

class Program
{
    // Function to find two non-repeating elements in array
    static void FindTwoNonRepeating(int[] arr, out int num1, out int num2)
    {
        int xor_all = 0;
        // XOR all elements to get xor of two unique numbers
        foreach (int num in arr)
        {
            xor_all ^= num; // accumulate XOR
        }

        // Find rightmost set bit in xor_all
        int set_bit = xor_all & (-xor_all); // isolates rightmost set bit

        num1 = 0;
        num2 = 0;

        // Divide elements into two groups and XOR separately
        foreach (int num in arr)
        {
            if ((num & set_bit) != 0)
                num1 ^= num; // XOR group with set bit
            else
                num2 ^= num; // XOR group without set bit
        }
    }

    static void Main()
    {
        int[] arr = { 2, 3, 7, 9, 2, 3 };
        FindTwoNonRepeating(arr, out int a, out int b);
        Console.WriteLine($"{a} -> {b}");
    }
}

xor_all ^= num; // accumulate XOR

XOR all elements to cancel pairs and get XOR of unique numbers

int set_bit = xor_all & (-xor_all); // isolates rightmost set bit

Find rightmost set bit to separate two unique numbers

if ((num & set_bit) != 0) num1 ^= num; else num2 ^= num;

Divide elements into two groups by set bit and XOR separately

Output

7 -> 9

Complexity Analysis

Time: O(n) because we traverse the array a constant number of times

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Naive approach uses nested loops or hash maps with O(n) space; XOR method is more space efficient

Edge Cases

Array with only two elements both unique

Returns those two elements directly

DSA C#

xor_all ^= num; // accumulate XOR

Array with duplicates but only two unique elements

Correctly finds the two unique elements by XOR grouping

DSA C#

if ((num & set_bit) != 0) num1 ^= num; else num2 ^= num;

Array where unique elements differ in the least significant bit

Rightmost set bit correctly separates them

DSA C#

int set_bit = xor_all & (-xor_all); // isolates rightmost set bit

When to Use This Pattern

When you see a problem asking to find two unique numbers among duplicates, reach for the XOR splitting pattern because it efficiently isolates them without extra space.

Common Mistakes

Mistake: Not isolating the rightmost set bit correctly, causing wrong grouping
Fix: Use 'xor_all & (-xor_all)' to get the rightmost set bit mask

Mistake: XORing all elements into one variable but not splitting into two groups
Fix: Split elements into two groups based on the set bit and XOR separately

Summary

Finds two unique numbers in an array where all others appear twice using XOR.

Use when you need to find exactly two non-repeating elements among duplicates efficiently.

The key insight is to XOR all elements, find a differing bit, and split the array to isolate each unique number.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where all other elements repeat twice?

easy

A. To cancel out all repeating elements and isolate the XOR of the two unique elements

B. To sort the array in ascending order

C. To count the frequency of each element

D. To reverse the array elements

Solution

1. Step 1: Understand XOR behavior with duplicates

   XOR of two identical numbers is 0, so XORing all elements cancels out duplicates.

2. Step 2: Result after XORing all elements

   The result is XOR of the two unique elements, isolating their combined difference.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option A

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR duplicates become zero, leaving unique elements XOR [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Confusing XOR with counting frequencies
• Assuming XOR reverses elements

2. Which of the following C# code snippets correctly initializes the XOR variable to start finding two non-repeating elements in an integer array arr?

easy

A. int xor = 0;

B. int xor = arr[0];

C. int xor = -1;

D. int xor = 1;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0 to accumulate XOR of all elements.

2. Step 2: Initialization correctness

   Initializing xor to 0 ensures correct cumulative XOR of array elements.

3. Final Answer:

   int xor = 0; -> Option A

4. Quick Check:

   Start XOR with 0 to accumulate values correctly [OK]

Hint: Start XOR with 0 because 0 ^ x = x [OK]

Common Mistakes:

• Starting XOR with 1 changes results
• Using negative numbers without reason
• Initializing with first array element causes errors

3. What will be the output of the following C# code snippet?

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

medium

A. 9

B. 0

C. 7

D. 14

Solution

1. Step 1: XOR all elements in the array

   Calculate xor = 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3. Since 2 ^ 2 = 0 and 3 ^ 3 = 0, this reduces to 7 ^ 9.

2. Step 2: Calculate XOR of remaining unique elements

   7 in binary: 0111, 9 in binary: 1001 XOR: 0111 ^ 1001 = 1110 (binary) = 14 (decimal).

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Duplicates cancel, XOR unique = 7 ^ 9 = 14 [OK]

Hint: Duplicates XOR to zero, XOR unique elements left [OK]

Common Mistakes:

• Forgetting duplicates cancel out
• Calculating XOR incorrectly
• Assuming output is one unique element

4. Identify the error in the following C# code snippet that attempts to find two non-repeating elements using XOR:

int[] arr = {4, 1, 2, 1, 2, 5};
int xor = 0;
foreach (int num in arr) {
    xor ^= num;
}
int setBit = xor & ~(xor - 1);
int x = 0, y = 0;
foreach (int num in arr) {
    if ((num & setBit) == 0)
        x ^= num;
    else
        y ^= num;
}
Console.WriteLine(x + ", " + y);

medium

A. The expression to find setBit is incorrect; it should be 'xor & (-xor)' instead of 'xor & ~(xor - 1)'

B. The initial xor should start with arr[0] instead of 0

C. No error; the code will output the two unique elements correctly

D. The if condition should check '(num & setBit) != 0' instead of '== 0'

Solution

1. Step 1: Check how setBit is calculated

   In two's complement, 'xor & ~(xor - 1)' is equivalent to 'xor & (-xor)', both isolate the rightmost set bit correctly.

2. Step 2: Verify code execution

   arr={4,1,2,1,2,5}, xor=4^5=1, setBit=1. Partitions: x=4 (evens), y=5 (odds). Outputs '4, 5' correctly.

3. Final Answer:

   No error; the code will output the two unique elements correctly -> Option C

4. Quick Check:

   Expressions equivalent, code partitions and XORs correctly [OK]

Hint: xor & ~(xor-1) == xor & -xor for rightmost set bit [OK]

Common Mistakes:

• Thinking 'xor & ~(xor-1)' differs from 'xor & -xor'
• Starting xor with first element instead of 0
• Confusing if condition for partitioning

5. Given an array arr = {10, 20, 10, 30, 40, 20}, write the final two non-repeating elements found using the XOR method. What are these elements?

hard

A. [10, 20]

B. [30, 40]

C. [10, 30]

D. [20, 40]

Solution

1. Step 1: XOR all elements to get combined XOR

   Calculate xor = 10 ^ 20 ^ 10 ^ 30 ^ 40 ^ 20. Duplicates cancel: 10 ^ 10 = 0, 20 ^ 20 = 0. Remaining xor = 30 ^ 40.

2. Step 2: Calculate XOR of 30 and 40

   30 in binary: 00011110, 40 in binary: 00101000 XOR: 00011110 ^ 00101000 = 00110110 (54 decimal). Use this to separate elements and find unique ones: 30 and 40.

3. Final Answer:

   [30, 40] -> Option B

4. Quick Check:

   Duplicates cancel, unique elements are 30 and 40 [OK]

Hint: Duplicates cancel, XOR leaves unique pair [OK]

Common Mistakes:

• Including duplicates as unique
• Mixing up XOR results
• Not cancelling duplicates properly