Two Non Repeating Elements in Array Using XOR in DSA C# - Time & Space Complexity

Time Complexity: Two Non Repeating Elements in Array Using XOR

O(n)

Understanding Time Complexity

We want to understand how the time needed grows when finding two unique numbers in an array using XOR.

How does the number of steps change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[] arr = {2, 3, 7, 9, 2, 3};
int xor = 0;
foreach (int num in arr) {
    xor ^= num;
}
int setBit = xor & (-xor);
int x = 0, y = 0;
foreach (int num in arr) {
    if ((num & setBit) != 0) x ^= num;
    else y ^= num;
}
Console.WriteLine($"Two unique elements are {x} and {y}");
    

This code finds two numbers that appear only once in an array where all others appear twice, using XOR operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops over the array.
• How many times: Each loop runs once over all elements, so twice in total.

How Execution Grows With Input

Each element is visited twice, so the total steps grow directly with the number of elements.

Input Size (n)	Approx. Operations
10	20
100	200
1000	2000

Pattern observation: The operations grow linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the number of elements in the array.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not nested, so their times add up, not multiply.

Interview Connect

Understanding this linear time approach shows you can solve problems efficiently by cleverly using bit operations and simple loops.

Self-Check

"What if the array had three unique elements instead of two? How would the time complexity change?"

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