Find the Only Non Repeating Element Using XOR in DSA Python

Mental Model

XORing a number with itself cancels it out to zero, so XORing all numbers leaves only the one that appears once.

Analogy: Imagine you have pairs of socks in a drawer. If you take out all socks and pair them up, only the single unmatched sock remains alone.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 -> 2
          2 ⊕ 3 -> 1
          1 ⊕ 2 -> 3
          3 ⊕ 4 -> 7
          7 ⊕ 3 -> 4
Result: 4 (the only non-repeating element)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the element that appears only once in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result to zero and combine with first number

Step 2: XOR result with second element 3

result = 2 ⊕ 3 = 1

Why: Combine next number to cancel pairs later

Step 3: XOR result with third element 2

result = 1 ⊕ 2 = 3

Why: XOR with repeated number cancels previous 2

Step 4: XOR result with fourth element 4

result = 3 ⊕ 4 = 7

Why: Add new number to result

Step 5: XOR result with fifth element 3

result = 7 ⊕ 3 = 4

Why: XOR with repeated 3 cancels it, leaving only 4

Result:

4 (the only non-repeating element)

Annotated Code

DSA Python

class Solution:
    def find_non_repeating(self, nums):
        result = 0
        for num in nums:
            result ^= num  # XOR accumulates unique element
        return result

if __name__ == "__main__":
    arr = [2, 3, 2, 4, 3]
    sol = Solution()
    print(sol.find_non_repeating(arr))

result ^= num # XOR accumulates unique element

XOR current number with result to cancel duplicates and keep unique

Output

4

Complexity Analysis

Time: O(n) because we traverse the array once

Space: O(1) because we use only one variable for XOR accumulation

vs Alternative: Better than using a hash map which uses O(n) space; XOR uses constant space

Edge Cases

Array with only one element

Returns that single element as it is the only one

DSA Python

No special guard needed; XOR with zero returns the element

Array where all elements except one appear twice

Correctly returns the unique element

DSA Python

XOR operation inherently handles this case

When to Use This Pattern

When you see a problem asking for the single unique element among duplicates, use XOR to cancel pairs efficiently.

Common Mistakes

Mistake: Using addition or subtraction instead of XOR to find unique element
Fix: Use XOR operator because it cancels duplicates correctly

Mistake: Initializing result with first element instead of zero
Fix: Initialize result to zero to correctly accumulate XOR of all elements

Summary

Finds the only element that does not repeat in an array using XOR.

Use when all elements except one appear twice and you want a fast, memory-efficient solution.

XORing duplicates cancels them out, leaving only the unique element.