Two Non Repeating Elements in Array Using XOR in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based Two Non Repeating Elements

What is the output of the following C# code that finds two non-repeating elements in an array using XOR?

DSA C#

using System;
class Program {
    static void Main() {
        int[] arr = {2, 3, 7, 9, 2, 3};
        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 + " -> null");
    }
}

A 7 -> 9 -> null

B 2 -> 3 -> null

C 9 -> 7 -> null

D 3 -> 2 -> null

💡 Hint

Focus on how XOR separates the two unique numbers by a set bit.

The XOR of all elements gives xor = 7 ^ 9. The setBit isolates a differing bit between 7 and 9. Partitioning the array by this bit separates 7 and 9, so x and y become 7 and 9 respectively. The output prints them in order found: 7 -> 9 -> null.

❓ Predict Output

intermediate

Result of XOR Partitioning Step

After computing xor and setBit in the XOR method, what is the value of setBit for the array {4, 1, 2, 1, 2, 5}?

DSA C#

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

A 4

B 1

C 5

D 0

💡 Hint

Look for the rightmost set bit in xor.

XOR of all elements is 4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 5 = 4 ^ 5 = 1 (since 1 ^ 1 and 2 ^ 2 cancel out). The rightmost set bit of 1 is 1, so setBit = 1.

🔧 Debug

advanced

Identify the Bug in XOR Two Non Repeating Elements Code

What error will the following code produce when run, and why?

DSA C#

int[] arr = {1, 2, 1, 3, 2, 5};
int xor = 0;
for (int i = 0; i <= arr.Length; i++) {
    xor ^= arr[i];
}
Console.WriteLine(xor);

A NullReferenceException due to uninitialized array

B No error, outputs XOR of all elements

C SyntaxError due to missing semicolon

D IndexOutOfRangeException because loop goes beyond array length

💡 Hint

Check the loop boundary condition carefully.

The loop uses i <= arr.Length which tries to access arr[arr.Length], an invalid index causing IndexOutOfRangeException.

🧠 Conceptual

advanced

Why XOR Helps Find Two Unique Elements

Why does XOR operation help in finding two non-repeating elements in an array where all other elements repeat twice?

A Because XOR adds all numbers together

B Because XOR sorts the array automatically

C Because XOR of two identical numbers is zero, so duplicates cancel out leaving XOR of unique elements

D Because XOR multiplies all numbers together

💡 Hint

Think about what happens when you XOR a number with itself.

XOR of a number with itself is zero, so pairs cancel out. The result is XOR of the two unique numbers, which helps separate them.

🚀 Application

expert

Number of Items in Resulting List After XOR Partition

Given the array {10, 20, 10, 30, 40, 20}, after applying the XOR method to find two unique elements, how many elements are in the list of numbers that have the set bit in the XOR result?

A 3

B 4

C 5

D 2

💡 Hint

Count how many numbers have the set bit in the XOR of unique elements.

XOR of all elements is 30 ^ 40 = 54. The rightmost set bit in 54 is 2 (binary 110110 & ~(110101) = 10). Numbers with this bit set are 10 (1010), 10 (1010), and 30 (11110). So 3 numbers have this bit set.

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