Two Non Repeating Elements in Array Using XOR in DSA C - 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 needed grows when finding two unique numbers in an array using XOR.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void findTwoNonRepeating(int arr[], int n, int *x, int *y) {
    int xor_all = 0;
    for (int i = 0; i < n; i++) {
        xor_all ^= arr[i];
    }
    int set_bit = xor_all & (-xor_all);
    *x = 0; *y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit)
            *x ^= arr[i];
        else
            *y ^= arr[i];
    }
}
    

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 that each go through the entire array once.
• How many times: Each loop runs exactly n times, where n is the array size.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly twice the size of the array because of two full passes.

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

Pattern observation: The operations grow linearly with input size, doubling because of two passes.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly in proportion to the number of elements in the 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 unique numbers instead of two? How would the time complexity change?"