Two Non Repeating Elements in Array Using XOR in DSA C# - Build from Scratch

Two Non Repeating Elements in Array Using XOR

📖 Scenario: Imagine you have a list of numbers where every number appears twice except for two unique numbers that appear only once. You want to find those two unique numbers quickly without using extra space.

🎯 Goal: Build a C# program that finds the two numbers that appear only once in an array where all other numbers appear twice, using the XOR operation.

📋 What You'll Learn

Create an integer array called numbers with the exact values: 2, 3, 7, 9, 2, 3

Create an integer variable called xorAll to store XOR of all elements

Use a for loop with variable i to XOR all elements in numbers and store in xorAll

Find the rightmost set bit of xorAll and store it in rightmostSetBit

Create two integer variables num1 and num2 initialized to 0

Use a for loop with variable i to separate numbers into two groups based on rightmostSetBit and XOR them into num1 and num2

Print the two unique numbers num1 and num2 separated by a space

💡 Why This Matters

🌍 Real World

Finding unique elements quickly is useful in error detection, data analysis, and network packet processing where duplicates are common.

💼 Career

Understanding bitwise operations and efficient algorithms is important for software developers working on performance-critical applications.

1

Create the array of numbers

Create an integer array called numbers with these exact values: 2, 3, 7, 9, 2, 3

DSA C#

// Create the array called numbers with the given values
// Your code here

Hint

Use int[] numbers = {2, 3, 7, 9, 2, 3}; to create the array.

2

Calculate XOR of all elements

Create an integer variable called xorAll and set it to 0. Then use a for loop with variable i to XOR all elements in numbers and store the result in xorAll

DSA C#

int[] numbers = {2, 3, 7, 9, 2, 3};
// Create xorAll and XOR all elements in numbers
// Your code here

Hint

Initialize xorAll to 0. Use a for loop to XOR each element with xorAll.

3

Find rightmost set bit and separate numbers

Create an integer variable called rightmostSetBit and set it to xorAll & (-xorAll). Then create two integer variables num1 and num2 initialized to 0. Use a for loop with variable i to iterate over numbers. If (numbers[i] & rightmostSetBit) != 0, XOR num1 with numbers[i], else XOR num2 with numbers[i]

DSA C#

int[] numbers = {2, 3, 7, 9, 2, 3};
int xorAll = 0;
for (int i = 0; i < numbers.Length; i++)
{
    xorAll ^= numbers[i];
}
// Find rightmost set bit
// Create num1 and num2
// Separate numbers into two groups and XOR
// Your code here

Hint

Use int rightmostSetBit = xorAll & (-xorAll); to find the rightmost set bit. Then separate numbers into two groups based on this bit and XOR them separately.

4

Print the two unique numbers

Print the two unique numbers num1 and num2 separated by a space using Console.WriteLine

DSA C#

int[] numbers = {2, 3, 7, 9, 2, 3};
int xorAll = 0;
for (int i = 0; i < numbers.Length; i++)
{
    xorAll ^= numbers[i];
}
int rightmostSetBit = xorAll & (-xorAll);
int num1 = 0, num2 = 0;
for (int i = 0; i < numbers.Length; i++)
{
    if ((numbers[i] & rightmostSetBit) != 0)
        num1 ^= numbers[i];
    else
        num2 ^= numbers[i];
}
// Print num1 and num2 separated by space
// Your code here

Hint

Use Console.WriteLine($"{num1} {num2}"); to print the two unique numbers separated by a space.

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