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

Time Complexity: Find the Only Non Repeating Element Using XOR

O(n)

Understanding Time Complexity

We want to know how fast we can find the single number that appears only once in a list where every other number appears twice.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def find_unique(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

This code finds the only number that does not repeat by using XOR on all elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the list grows, the number of XOR operations grows 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 work grows in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Since XOR is a bitwise operation, it must be constant time regardless of input size."

[OK] Correct: While XOR itself is fast, it is done once per element, so total time depends on how many elements there are.

Interview Connect

Understanding this approach shows you can use clever tricks to solve problems efficiently, a skill valued in many coding challenges.

Self-Check

"What if the array was sorted? Could we find the unique element faster than O(n)?"