Find the Only Non Repeating Element Using XOR in DSA C - Time & Space Complexity

Time Complexity: Find the Only Non Repeating Element Using XOR

O(n)

Understanding Time Complexity

We want to know how the time needed to find the unique element changes as the list grows.

How many steps does it take to find the only number that does not repeat?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the only non-repeating element by XORing all elements in the array.

Identify Repeating Operations

• Primary operation: XOR operation inside a single loop.
• How many times: Exactly once for each element in the array (n times).

How Execution Grows With Input

Each new element adds one XOR operation, so the total steps grow directly with the number of elements.

Input Size (n)	Approx. Operations
10	10 XOR operations
100	100 XOR operations
1000	1000 XOR operations

Pattern observation: The number of operations grows in a straight line as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the unique element grows directly with the number of elements in the array.

Common Mistake

[X] Wrong: "Since XOR is a simple operation, the time is constant no matter the input size."

[OK] Correct: Even though XOR itself is fast, it must be done for every element, so the total time depends on how many elements there are.

Interview Connect

Understanding this simple but powerful approach shows you can use bitwise operations to solve problems efficiently, a skill valued in many coding challenges.

Self-Check

"What if the array was sorted? Would the time complexity to find the unique element change?"