Two Non Repeating Elements in Array Using XOR in DSA C# - Deep Dive

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

This topic teaches how to find two unique numbers in an array where every other number repeats exactly twice. We use a special operation called XOR to do this efficiently without extra memory. XOR helps us cancel out pairs and isolate the unique numbers. This method is faster and uses less space than checking each number one by one.

Why it matters

Without this method, finding unique numbers among duplicates would require extra memory or slower searching. This XOR approach solves the problem quickly and with minimal resources, which is important in real-world applications like error detection and data analysis. It helps computers handle large data sets efficiently.

Where it fits

Before learning this, you should understand basic arrays and the XOR operation. After this, you can explore more complex bit manipulation techniques and problems involving unique elements or sets.

Mental Model

Core Idea

Using XOR, pairs of identical numbers cancel out, leaving only the unique numbers visible through bit differences.

Think of it like...

Imagine you have pairs of gloves mixed in a box, except two gloves have no pair. If you shake the box and every matching pair cancels out, only the two unmatched gloves remain to be found.

Array: [2, 3, 7, 9, 2, 3]
Step 1: XOR all elements -> 7 ^ 9 = 14 (binary 1110)
Step 2: Find rightmost set bit in 14 -> bit mask 2 (binary 0010)
Step 3: Divide array into two groups by this bit:
  Group 1 (bit set): 7, 9
  Group 2 (bit not set): 2, 3, 2, 3
Step 4: XOR each group:
  Group 1 XOR -> 7 (pairs cancel, leaving 7)
  Group 2 XOR -> 9
Result: Unique numbers are 7 and 9

Build-Up - 7 Steps

1

Foundation

Understanding XOR Operation Basics

Concept: Learn what XOR does and how it behaves with pairs and zero.

XOR (^) compares two bits: if they are different, result is 1; if same, result is 0. Examples: 0 ^ 0 = 0 1 ^ 0 = 1 1 ^ 1 = 0 Properties: - x ^ x = 0 (a number XOR itself is zero) - x ^ 0 = x (a number XOR zero is the number itself) - XOR is commutative and associative, so order doesn't matter.

Result

Knowing XOR lets you cancel pairs of identical numbers by XORing them together.

Understanding XOR's canceling property is key to isolating unique elements in arrays.

2

Foundation

Problem Setup: Array with Two Unique Numbers

Concept: Recognize the problem where all numbers repeat twice except two unique ones.

Given an array like [2, 3, 7, 9, 2, 3], every number except two appears twice. Goal: Find those two unique numbers efficiently. Naive ways include using extra memory or nested loops, which are slow or costly.

Result

Clear problem statement: find two numbers that appear once in an array of duplicates.

Framing the problem helps focus on efficient solutions using XOR instead of brute force.

3

Intermediate

XOR All Elements to Find Combined Difference

🤔Before reading on: Do you think XORing all elements gives one unique number or a combination? Commit to your answer.

Concept: XORing all elements cancels duplicates and leaves XOR of the two unique numbers.

Step 1: XOR all array elements. Example: 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 Pairs cancel: (2 ^ 2) = 0, (3 ^ 3) = 0 Result: 7 ^ 9 = 14 (binary 1110) This combined XOR shows bits where the two unique numbers differ.

Result

Combined XOR value representing bit differences between the two unique numbers.

Knowing the combined XOR helps us separate the two unique numbers by their differing bits.

4

Intermediate

Find Rightmost Set Bit to Separate Groups

🤔Before reading on: Will any set bit in combined XOR work to separate numbers? Commit to your answer.

Concept: Find a bit where the two unique numbers differ to split the array into two groups.

Find rightmost set bit in combined XOR (e.g., 14 = 1110, rightmost set bit is 2 = 0010). Use this bit as a mask to divide numbers: Group 1: Numbers with this bit set Group 2: Numbers without this bit set Because unique numbers differ at this bit, they fall into different groups.

Result

Two groups where each unique number is isolated in separate groups.

Separating numbers by a differing bit isolates unique numbers for independent XOR.

5

Intermediate

XOR Each Group to Find Unique Numbers

Concept: XOR numbers in each group to cancel duplicates and find unique numbers.

XOR all numbers in Group 1 -> duplicates cancel, leaving one unique number. XOR all numbers in Group 2 -> duplicates cancel, leaving the other unique number. Example: Group 1: 7, 9 -> XOR = 14 Group 2: 2, 3, 2, 3 -> XOR = 0 Unique numbers are 7 and 9.

Result

Two unique numbers extracted from the array.

XOR within groups leverages cancellation to reveal unique elements without extra memory.

6

Advanced

Complete C# Implementation with Comments

🤔Before reading on: Can you predict the output of the code for input [2,3,7,9,2,3]? Commit to your answer.

Concept: Implement the full XOR-based solution in C# with clear steps and comments.

using System; class Program { static void FindTwoUnique(int[] arr) { int xorAll = 0; foreach (int num in arr) { xorAll ^= num; // XOR all elements } int rightmostSetBit = xorAll & (-xorAll); // isolate rightmost set bit int num1 = 0, num2 = 0; foreach (int num in arr) { if ((num & rightmostSetBit) != 0) { num1 ^= num; // XOR group with bit set } else { num2 ^= num; // XOR group without bit set } } Console.WriteLine($"Unique numbers are: {num1} and {num2}"); } static void Main() { int[] arr = {2, 3, 7, 9, 2, 3}; FindTwoUnique(arr); } }

Result

Unique numbers are: 7 and 9

Seeing the full code connects theory to practice and confirms the XOR approach works end-to-end.

7

Expert

Why XOR Approach Is Optimal and Its Limitations

🤔Before reading on: Do you think this XOR method works if more than two numbers are unique? Commit to your answer.

Concept: Understand why XOR is efficient and where it fails for more complex cases.

XOR approach runs in O(n) time and O(1) space, making it very efficient. It relies on exactly two unique numbers; if more unique numbers exist, this method fails. For more unique numbers, other methods like hash maps or sorting are needed. Also, XOR works best with integers and bitwise operations, not with complex data types.

Result

Clear understanding of XOR method's efficiency and its boundary conditions.

Knowing the method's limits prevents misuse and guides choosing the right tool for different problems.

Under the Hood

XOR compares bits of numbers. When XORing duplicates, bits cancel to zero. The combined XOR of two unique numbers highlights bits where they differ. Using the rightmost set bit isolates one differing bit, allowing separation of numbers into two groups. XORing each group cancels duplicates, leaving unique numbers. This works because XOR is associative, commutative, and self-inverse.

Why designed this way?

This method was designed to solve the problem in linear time and constant space, avoiding extra memory like hash tables. Bitwise XOR operations are fast and supported at hardware level. Alternatives like sorting or hash maps use more time or space. The approach exploits XOR's unique properties to elegantly isolate unique elements.

Input Array
  ┌─────────────────────────────┐
  │ 2, 3, 7, 9, 2, 3            │
  └─────────────┬───────────────┘
                │ XOR all elements
                ▼
          Combined XOR = 14 (1110)
                │ Find rightmost set bit
                ▼
          Bit mask = 2 (0010)
                │ Split into groups
       ┌────────┴─────────┐
       │                  │
Group 1 (bit set)    Group 2 (bit not set)
  7, 9                 2, 3, 2, 3
       │                  │
       ▼                  ▼
  XOR group 1 = 14    XOR group 2 = 0
       │                  │
       └────────┬─────────┘
                ▼
       Unique numbers: 7 and 9

Myth Busters - 3 Common Misconceptions

Quick: Does XORing all elements give you the two unique numbers directly? Commit yes or no.

Common Belief: XORing all elements directly reveals the two unique numbers separately.

Reality: XORing all elements gives the XOR of the two unique numbers combined, not the numbers themselves.

Why it matters: Misunderstanding this leads to confusion and incorrect attempts to extract unique numbers without further steps.

Quick: Can this XOR method find three or more unique numbers in the array? Commit yes or no.

Common Belief: The XOR method works for any number of unique elements in the array.

Reality: This XOR method only works when exactly two unique numbers exist; it fails with more unique numbers.

Why it matters: Using this method on arrays with more unique numbers results in wrong answers and wasted effort.

Quick: Does the position of the rightmost set bit matter when splitting groups? Commit yes or no.

Common Belief: Any set bit in the combined XOR can be used to split the array into groups.

Reality: While any set bit can work, choosing the rightmost set bit is a simple and efficient way to isolate a differing bit.

Why it matters: Choosing bits arbitrarily can complicate implementation and reduce clarity.

Expert Zone

1

The choice of rightmost set bit is a convention for simplicity; any set bit differing between unique numbers works but complicates code.

2

XOR operations are extremely fast at hardware level, making this approach optimal for large data sets where memory is limited.

3

This method assumes integer data types; extending it to other data types requires custom bitwise representations or different algorithms.

When NOT to use

Do not use this XOR method if there are more than two unique numbers or if the data type is non-integer. Instead, use hash maps or sorting-based methods for multiple unique elements or complex data types.

Production Patterns

This XOR technique is used in embedded systems and performance-critical applications where memory is limited. It also appears in coding interviews to test bit manipulation skills and in error detection algorithms where unique patterns must be isolated quickly.

Connections

Bit Manipulation

Builds-on

Understanding XOR for unique elements deepens knowledge of bit manipulation techniques used in many algorithms.

Hash Tables

Alternative approach

Knowing XOR method helps appreciate when hash tables are needed for more complex uniqueness problems.

Signal Processing

Similar pattern

XOR's canceling property is analogous to noise cancellation in signals, where unwanted repeated patterns are removed to isolate unique signals.

Common Pitfalls

#1 Trying to find unique numbers by XORing all elements and returning the result directly.

Wrong approach:

int xorAll = 0;
foreach (int num in arr) {
xorAll ^= num;
}
Console.WriteLine($"Unique numbers: {xorAll}");

Correct approach:

int xorAll = 0;
foreach (int num in arr) {
xorAll ^= num;
}
int rightmostSetBit = xorAll & (-xorAll);
int num1 = 0, num2 = 0;
foreach (int num in arr) {
if ((num & rightmostSetBit) != 0) num1 ^= num;
else num2 ^= num;
}
Console.WriteLine($"Unique numbers: {num1} and {num2}");

Root cause:

Misunderstanding that XOR of all elements combines the two unique numbers instead of separating them.

#2 Using this XOR method on arrays with more than two unique numbers.

Wrong approach:

int[] arr = {1, 2, 3, 2, 1, 4};
// Using XOR method expecting to find all unique numbers
// This will fail or give incorrect results.

Correct approach:

Use a hash map or dictionary to count occurrences and find all unique numbers:
var counts = new Dictionary();
foreach (var num in arr) {
if (counts.ContainsKey(num)) counts[num]++;
else counts[num] = 1;
}
foreach (var kvp in counts) {
if (kvp.Value == 1) Console.WriteLine(kvp.Key);
}

Root cause:

Assuming XOR method generalizes beyond two unique numbers.

Key Takeaways

XOR operation cancels pairs of identical numbers, leaving only unique elements visible through bit differences.

Finding the rightmost set bit in the combined XOR helps split numbers into groups to isolate unique numbers.

XOR-based method finds exactly two unique numbers in linear time and constant space, making it efficient and elegant.

This method only works for two unique numbers; for more unique elements, other approaches like hash maps are needed.

Understanding bitwise operations and their properties unlocks powerful techniques for solving array uniqueness problems.

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