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 twice. We use a special operation called XOR to do this efficiently without extra space. The method helps identify the two numbers that appear only once among duplicates. It is a clever way to solve this problem faster than checking each number one by one.

Why it matters

Without this method, finding two unique numbers among duplicates would require extra memory or slower searching. This XOR approach saves time and space, making programs faster and more efficient. It is useful in real-world tasks like error detection, data analysis, and security where unique elements matter. Without it, systems would be slower and use more resources.

Where it fits

Before learning this, you should understand basic arrays and the XOR operation. After this, you can explore more complex bit manipulation problems and algorithms that find unique or missing elements in data. This topic builds a foundation for efficient problem-solving using bitwise operations.

Mental Model

Core Idea

Using XOR properties, we can isolate two unique numbers in a list where all others appear twice by separating numbers based on a differing bit.

Think of it like...

Imagine you have a box of pairs of gloves except two single gloves that don't have a match. By looking at a specific feature like color or size that differs between the two singles, you can separate the gloves into two groups and find the unique ones easily.

Array: [a, a, b, b, x, y]
Step 1: XOR all elements -> xor = x ^ y
Step 2: Find rightmost set bit in xor -> mask
Step 3: Divide elements into two groups by mask bit
Group 1: elements with bit set
Group 2: elements with bit not set
Step 4: XOR each group separately to get x and y

  ┌───────────────┐
  │  Input Array  │
  │ a a b b x y   │
  └──────┬────────┘
         │ XOR all
         ▼
  ┌───────────────┐
  │ xor = x ^ y   │
  └──────┬────────┘
         │ Find rightmost set bit
         ▼
  ┌───────────────┐
  │ mask          │
  └──────┬────────┘
         │ Split array by mask bit
         ▼
  ┌───────────────┐     ┌───────────────┐
  │ Group 1       │     │ Group 2       │
  │ (bit set)     │     │ (bit not set) │
  └──────┬────────┘     └──────┬────────┘
         │ XOR elements          │ XOR elements
         ▼                      ▼
      unique x               unique y

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does and its key properties.

XOR (^) compares two bits and returns 1 if they differ, 0 if they are the same. Key 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 (order doesn't matter) Example: 5 (0101) ^ 3 (0011) = 6 (0110)

Result

Knowing XOR basics lets you combine numbers to cancel duplicates and isolate unique values.

Understanding XOR's canceling effect is the foundation for finding unique elements efficiently.

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], numbers 7 and 9 appear once, others twice. Goal: Find 7 and 9 without extra space or sorting. Naive ways: Use extra memory or nested loops (slow). We want a fast, memory-efficient method.

Result

Clear problem understanding helps focus on efficient XOR-based solution.

Knowing the problem constraints guides us to use XOR properties smartly.

3

Intermediate

XOR All Elements to Combine Uniques

🤔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 two unique numbers.

Example array: [2, 3, 7, 9, 2, 3] XOR all: 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 = (2 ^ 2) ^ (3 ^ 3) ^ 7 ^ 9 = 0 ^ 0 ^ 7 ^ 9 = 7 ^ 9 This result is not a single number but XOR of the two unique numbers.

Result

xor = 7 ^ 9 = 14 (1110 in binary)

XORing all elements reduces the problem to separating two unique numbers combined by XOR.

4

Intermediate

Find Rightmost Set Bit to Separate Groups

🤔Before reading on: Do you think any set bit in xor can separate the two unique numbers? Commit to your answer.

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

xor = 14 (1110) Rightmost set bit can be found by: mask = xor & (-xor) For 14: -14 in binary (two's complement) = 11110010 (for 8-bit representation) 14 & (-14) = 2 (0010) This bit is set in one unique number and not in the other. We use this mask to divide numbers.

Result

mask = 2 (bit position 2) This bit separates unique numbers into different groups.

Finding a differing bit lets us split numbers so each unique number falls into a separate group.

5

Intermediate

Divide Array and XOR Each Group

🤔Before reading on: Will XORing each group give the unique numbers or something else? Commit to your answer.

Concept: Split array by mask bit and XOR each group to isolate unique numbers.

Group 1: numbers with mask bit set Group 2: numbers without mask bit set Example: Array: [2, 3, 7, 9, 2, 3] mask = 2 Group 1 (bit set): 2 (10), 2 (10), 3 (11), 3 (11), 7 (111) Group 2 (bit not set): 9 (1001) XOR Group 1: 2 ^ 2 ^ 3 ^ 3 ^ 7 = 7 XOR Group 2: 9 Unique numbers: 7 and 9

Result

Unique numbers found: 7 and 9

Separating by differing bit and XORing groups isolates each unique number perfectly.

6

Advanced

Complete C Code Implementation

🤔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 to find two unique numbers.

#include void findTwoUnique(int arr[], int n, int *x, int *y) { int xor = 0; for (int i = 0; i < n; i++) { xor ^= arr[i]; } int mask = xor & (-xor); *x = 0; *y = 0; for (int i = 0; i < n; i++) { if (arr[i] & mask) *x ^= arr[i]; else *y ^= arr[i]; } } int main() { int arr[] = {2, 3, 7, 9, 2, 3}; int n = sizeof(arr)/sizeof(arr[0]); int x, y; findTwoUnique(arr, n, &x, &y); printf("Two unique elements are %d and %d\n", x, y); return 0; }

Result

Two unique elements are 7 and 9

Seeing the full code ties together all steps and shows practical application of XOR to solve the problem efficiently.

7

Expert

Why XOR Method is Optimal and Its Limits

🤔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 works perfectly for two unique numbers and where it fails.

XOR cancels pairs perfectly because x ^ x = 0. When exactly two numbers are unique, their XOR is non-zero and has at least one set bit. This bit helps split numbers into two groups. If more than two numbers are unique, XOR of all unique numbers may not help separate them cleanly. This method is optimal for exactly two unique numbers but not for more. For more unique numbers, other methods like hash maps or sorting are needed.

Result

XOR method is fast and memory efficient only for two unique numbers, not more.

Knowing the method's limits prevents misuse and guides choosing correct algorithms for different problems.

Under the Hood

XOR operation works at the bit level, comparing each bit of two numbers. When XORing all array elements, pairs cancel out because identical bits produce zero. The remaining XOR is the combination of two unique numbers. Finding the rightmost set bit in this XOR identifies a bit where these two numbers differ. Splitting the array by this bit groups numbers so that each unique number falls into a separate group. XORing each group isolates the unique numbers because duplicates cancel out within groups.

Why designed this way?

This method was designed to solve the problem in linear time and constant space, avoiding extra memory like hash tables. XOR's properties naturally cancel duplicates, making it ideal. Alternatives like sorting or hash maps use more time or space. The bitwise approach is elegant and efficient, leveraging hardware-level operations for speed.

Input Array
  │
  ▼
XOR all elements
  │
  ▼
Combined XOR of two uniques
  │
  ▼
Find rightmost set bit (mask)
  │
  ▼
Split array into two groups by mask bit
  │          │
  ▼          ▼
Group 1     Group 2
  │          │
  ▼          ▼
XOR group 1 XOR group 2
  │          │
  ▼          ▼
Unique 1    Unique 2

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 gives 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: Believing this leads to confusion and incorrect attempts to extract unique numbers without further steps.

Quick: Can this XOR method find unique numbers if there are three or more unique elements? 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 correctly when exactly two numbers are unique; it fails for more unique numbers.

Why it matters: Using this method for more unique numbers results in wrong answers and wasted debugging time.

Quick: Is the rightmost set bit always the best choice to split the array? Commit yes or no.

Common Belief: Any set bit in the XOR can be used to split the array equally well.

Reality: The rightmost set bit is chosen for simplicity and guaranteed to exist; other set bits can also work but complicate implementation.

Why it matters: Choosing bits arbitrarily can cause inconsistent grouping and bugs.

Expert Zone

1

The choice of rightmost set bit is a simple heuristic; other set bits can be used but require careful handling.

2

The method assumes exactly two unique numbers; if input violates this, results are unpredictable.

3

Bitwise operations are hardware-accelerated, making this method faster than hash-based approaches in practice.

When NOT to use

Do not use this XOR method if the array has more than two unique numbers or if duplicates appear more than twice. Instead, use hash maps or sorting-based methods for those cases.

Production Patterns

This XOR technique is used in embedded systems and performance-critical code where memory is limited. It also appears in coding interviews to test understanding of bitwise operations and problem-solving skills.

Connections

Bit Manipulation

Builds-on

Mastering XOR for this problem deepens understanding of bit manipulation techniques used in many algorithms.

Hash Tables

Alternative approach

Knowing XOR method helps appreciate when hash tables are needed and when bitwise tricks are more efficient.

Error Detection in Communication

Similar pattern

XOR is used in error detection codes like parity checks, showing how this concept applies beyond arrays to real-world data integrity.

Common Pitfalls

#1 Assuming XOR of all elements directly gives unique numbers.

Wrong approach:

int xor = 0;
for (int i = 0; i < n; i++) {
xor ^= arr[i];
}
printf("Unique numbers: %d and %d", xor, xor);

Correct approach:

int xor = 0;
for (int i = 0; i < n; i++) {
xor ^= arr[i];
}
int mask = xor & (-xor);
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (arr[i] & mask)
x ^= arr[i];
else
y ^= arr[i];
}
printf("Unique numbers: %d and %d", x, y);

Root cause:

Misunderstanding that XOR of all elements combines the two unique numbers, not separates them.

#2 Using this method when more than two unique numbers exist.

Wrong approach:

Applying the same XOR splitting logic on array with three unique numbers expecting correct results.

Correct approach:

Use hash maps or sorting to find unique numbers when count is more than two.

Root cause:

Not recognizing the method's limitation to exactly two unique numbers.

#3 Not finding the rightmost set bit correctly.

Wrong approach:

int mask = xor & (xor - 1); // Incorrect way to find set bit

Correct approach:

int mask = xor & (-xor); // Correct way to find rightmost set bit

Root cause:

Confusing bit manipulation operations and their effects.

Key Takeaways

XOR operation cancels out pairs and helps isolate unique elements efficiently.

Finding the rightmost set bit in XOR of two unique numbers allows splitting the array into two groups.

XORing each group separately reveals the two unique numbers without extra memory.

This method works only when exactly two numbers are unique; more unique numbers require different approaches.

Understanding bitwise operations unlocks powerful, efficient solutions for many array problems.