Two Non Repeating Elements in Array Using XOR in DSA Python - Time & Space Complexity

Time Complexity: Two Non Repeating Elements in Array Using XOR

O(n)

Understanding Time Complexity

We want to understand how the time taken grows when finding two unique numbers in an array where every other number repeats.

How does the number of steps change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def two_non_repeating(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num

    set_bit = xor_all & (-xor_all)

    x = 0
    y = 0
    for num in arr:
        if num & set_bit:
            x ^= num
        else:
            y ^= num

    return x, y
    

This code finds two numbers that appear only once in an array where all others appear twice, using XOR operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops over the array to perform XOR operations.
• How many times: Each loop runs once over all elements, so twice in total.

How Execution Grows With Input

Each element is processed twice, so the total steps grow directly with the number of elements.

Input Size (n)	Approx. Operations
10	About 20 XOR operations
100	About 200 XOR operations
1000	About 2000 XOR operations

Pattern observation: Doubling the input roughly doubles the number of operations.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not nested, so their times add up, not multiply.

Interview Connect

Understanding this linear time approach shows you can solve problems efficiently by clever use of bit operations, a skill valued in many coding challenges.

Self-Check

"What if the array had three non-repeating elements instead of two? How would the time complexity change?"