Why Find the Only Non Repeating Element Using XOR in DSA C?

The Big Idea

What if you could find the odd one out in a crowd with just one simple trick?

The Scenario

Imagine you have a box full of socks where every sock has a matching pair except one. You want to find that single sock without checking each pair one by one.

The Problem

Checking each sock manually to find the one without a pair takes a lot of time and can easily lead to mistakes, especially if the box is large. You might lose track or miss a sock.

The Solution

Using XOR, you can quickly find the single sock without a pair by combining all socks in a way that pairs cancel out, leaving only the unique one.

Before vs After

✗ Before

int findUnique(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int count = 0;
        for (int j = 0; j < size; j++) {
            if (arr[i] == arr[j]) count++;
        }
        if (count == 1) return arr[i];
    }
    return -1;
}

✓ After

int findUnique(int arr[], int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        result ^= arr[i];
    }
    return result;
}

What It Enables

This method allows you to find the unique element in a list instantly, no matter how large the list is.

Real Life Example

Finding the one defective product in a batch where all others are identical, without checking each product twice.

Key Takeaways

Manual checking is slow and error-prone.

XOR cancels out pairs and reveals the unique element.

Efficient and simple solution for finding a single non-repeating item.