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.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where every other element repeats 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 property for 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 because duplicates cancel out.

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
• Using XOR to count 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?

easy

A. int xor = 1;

B. int xor = 0;

C. int xor = -1;

D. int xor = NULL;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0.

2. Step 2: Initialize XOR variable

   Setting xor = 0 allows XORing all elements correctly.

3. Final Answer:

   int xor = 0; -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 because 0 XOR x = x [OK]

Common Mistakes:

• Initializing XOR with 1 or -1
• Using NULL for integer variable
• Not initializing XOR variable

3. What will be the output of the following C code snippet?

int arr[] = {2, 3, 7, 9, 2, 3};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
printf("%d", xor);

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements in the array

   Calculate 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result after XORing all elements

   The final XOR value is 14, which is XOR of the two unique elements 7 and 9.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR all elements to get XOR of unique pair [OK]

Common Mistakes:

• Stopping XOR early
• Miscomputing XOR values
• Assuming output is one unique element

4. Identify the error in the following code snippet that attempts to find two non-repeating elements using XOR:

int arr[] = {4, 1, 2, 1, 2, 5};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
int set_bit = xor & ~(xor - 1);
int x = 0, y = 0;
for(int i = 0; i < 6; i++) {
    if(arr[i] & set_bit)
        x ^= arr[i];
    else
        y ^= arr[i];
}
printf("%d %d", x, y);

medium

A. Incorrect calculation of set_bit using xor & ~(xor - 1)

B. Loop range should be 0 to 5, not 0 to 6

C. Missing initialization of x and y to zero

D. No error, code works correctly

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly finds rightmost set bit.

2. Step 2: Verify loops and initialization

   Loops run from 0 to 5 (6 elements), x and y initialized to 0 correctly.

3. Final Answer:

   No error, code works correctly -> Option D

4. Quick Check:

   Code logic and syntax are correct [OK]

Hint: Check bitwise operations and loop ranges carefully [OK]

Common Mistakes:

• Miscomputing set_bit
• Wrong loop boundaries
• Uninitialized variables

5. Given an array where exactly two elements appear once and all others appear twice, how can you find those two unique elements efficiently using XOR? Choose the correct sequence of steps.

hard

A. Sort the array, then scan to find unique elements

B. Use a hash map to count frequencies, then pick elements with count 1

C. XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately

D. XOR all elements twice to get unique elements

Solution

1. Step 1: XOR all elements to get XOR of two unique elements

   This cancels out duplicates and leaves XOR of unique pair.

2. Step 2: Find rightmost set bit in XOR result

   This bit differs between the two unique elements.

3. Step 3: Divide elements into two groups based on this bit and XOR each group

   This separates the two unique elements and finds them individually.

4. Final Answer:

   XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately -> Option C

5. Quick Check:

   Use XOR and bit partitioning to find unique elements [OK]

Hint: Use XOR and bit mask to split and find unique elements [OK]

Common Mistakes:

• Sorting instead of XOR
• Using hash map (extra space)
• XORing twice without grouping