Find the Only Non Repeating Element Using XOR in DSA C - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

For each element in array

↓

Apply XOR: result = result XOR element

↓

Repeat for all elements

↓

Result holds the non-repeating element

↓

Return result

We start with zero and XOR it with every element in the array. Pairs cancel out, leaving only the unique element.

Execution Sample

DSA C

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 element that does not repeat by XORing all elements.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State
1	Initialize result	N/A	N/A	0	result=0
2	XOR with arr[0]	2	0	2	result=2
3	XOR with arr[1]	3	2	1	result=1 (2^3=1)
4	XOR with arr[2]	2	1	3	result=3 (1^2=3)
5	XOR with arr[3]	4	3	7	result=7 (3^4=7)
6	XOR with arr[4]	3	7	4	result=4 (7^3=4)
7	XOR with arr[5]	4	4	0	result=0 (4^4=0)
8	XOR with arr[6]	5	0	5	result=5 (0^5=5)
9	End of array	N/A	5	5	Unique element found: 5

💡 All pairs XOR to 0, leaving the unique element 5 in result.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	N/A	2	1	3	7	4	0	5	5
i	N/A	0	1	2	3	4	5	6	End

Key Moments - 3 Insights

Why does XORing pairs of the same number result in zero?

Because XOR of a number with itself is zero, as shown in steps 6 and 7 where result XOR 4 twice cancels out to zero.

Why do we start result with zero?

Zero is the identity for XOR, so XORing zero with any number returns that number, as in step 2.

How does XOR help find the unique element?

All repeating elements cancel out because XORing a number twice is zero, leaving only the unique element, as seen in the final result 5.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of result after XORing with arr[3]?

A 3

B 7

C 4

D 1

💡 Hint

Check Step 5 in the execution_table where arr[3] = 4 is XORed.

At which step does the result become zero during the XOR process?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the 'Result After XOR' column in Step 7.

If the array had no unique element, what would the final result be?

A Zero

B The first element

C The last element

D Undefined

💡 Hint

Pairs XOR to zero, so no unique element means result ends at zero (see exit_note).

Concept Snapshot

Find unique element by XORing all array elements.
XOR pairs cancel out to zero.
Start with result = 0.
Final result is the unique element.
Works only if every other element repeats exactly twice.

Full Transcript

This concept finds the only non-repeating element in an array by using XOR operation. We start with a variable result set to zero. Then we XOR result with each element in the array one by one. Because XOR of a number with itself is zero, all repeating elements cancel out. The only element that does not repeat remains in result at the end. This method is efficient and uses constant extra space.