Two Non Repeating Elements in Array Using XOR in DSA Python

Mental Model

Use XOR to cancel out pairs and isolate two unique numbers by splitting based on a differing bit.

Analogy: Imagine you have pairs of socks mixed in a pile except two socks that don't have a pair. By looking at a specific color stripe that only one of the unique socks has, you can separate the pile into two groups and find each unique sock.

Array: [2, 3, 7, 9, 2, 3]
Unique elements: 7 and 9
XOR all: 2⊕3⊕7⊕9⊕2⊕3 = 7⊕9
Find rightmost set bit in XOR result to split array into two groups
Group 1 -> elements with that bit set
Group 2 -> elements without that bit set

Dry Run Walkthrough

Input: array: [2, 3, 7, 9, 2, 3]

Goal: Find the two numbers that appear only once (7 and 9) using XOR operations

Step 1: XOR all elements to get xor_all

2 ⊕ 3 ⊕ 7 ⊕ 9 ⊕ 2 ⊕ 3 = 14 (binary 1110)

Why: XOR cancels pairs, leaving XOR of two unique numbers

Step 2: Find rightmost set bit in xor_all (14) -> bit_mask = 2 (binary 0010)

bit_mask = 2

Why: This bit differs between the two unique numbers, used to separate them

Step 3: Divide array into two groups based on bit_mask and XOR each group

Group 1 (bit set): 3, 7, 3
Group 2 (bit not set): 2, 9, 2

Why: Separating numbers so pairs cancel within groups, leaving unique numbers isolated

Step 4: XOR Group 1: 3 ⊕ 7 ⊕ 3 = 7

Group 1 XOR result = 7

Why: Pairs cancel out to zero, leaving 7

Step 5: XOR Group 2: 2 ⊕ 9 ⊕ 2 = 9

Group 2 XOR result = 9

Why: Pairs cancel, leaving XOR of unique numbers in this group

Result:

Unique elements are 7 and 9 (14 in decimal is XOR of 7 and 9, final unique numbers found by group XOR)

Annotated Code

DSA Python

class Solution:
    def two_non_repeating(self, arr):
        xor_all = 0
        for num in arr:
            xor_all ^= num  # XOR all elements to get xor of two unique numbers

        bit_mask = xor_all & (-xor_all)  # Get rightmost set bit to separate groups

        num1 = 0
        num2 = 0
        for num in arr:
            if num & bit_mask:
                num1 ^= num  # XOR group with bit set
            else:
                num2 ^= num  # XOR group without bit set

        return num1, num2


if __name__ == '__main__':
    arr = [2, 3, 7, 9, 2, 3]
    sol = Solution()
    result = sol.two_non_repeating(arr)
    print(f"{result[0]} -> {result[1]} -> null")

xor_all ^= num # XOR all elements to get xor of two unique numbers

XOR accumulates all numbers to isolate XOR of unique elements

bit_mask = xor_all & (-xor_all) # Get rightmost set bit to separate groups

Find rightmost set bit to split numbers into two groups

if num & bit_mask: num1 ^= num # XOR group with bit set else: num2 ^= num # XOR group without bit set

Separate and XOR numbers by bit_mask to isolate unique numbers

return num1, num2

Return the two unique numbers found

Output

7 -> 9 -> null

Complexity Analysis

Time: O(n) because we traverse the array a few times but only linearly

Space: O(1) because we use only a few variables regardless of input size

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

Edge Cases

Array with only two elements (both unique)

Returns those two elements correctly

DSA Python

xor_all ^= num  # XOR all elements to get xor of two unique numbers

Array with duplicates and two unique elements at start or end

Still correctly identifies the two unique elements

DSA Python

if num & bit_mask:
    num1 ^= num  # XOR group with bit set
else:
    num2 ^= num  # XOR group without bit set

Array where unique elements differ in the least significant bit

Rightmost set bit correctly separates them

DSA Python

bit_mask = xor_all & (-xor_all)  # Get rightmost set bit to separate groups

When to Use This Pattern

When you see a problem asking to find two unique numbers among duplicates, reach for the XOR splitting pattern because it efficiently isolates them without extra space.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly, causing wrong grouping
Fix: Use bit_mask = xor_all & (-xor_all) to get the correct separating bit

Mistake: Mixing up which group to XOR, leading to incorrect unique numbers
Fix: Ensure numbers are separated by checking if num & bit_mask is true or false

Summary

Finds two unique numbers in an array where all others appear twice using XOR.

Use when you need to find exactly two non-repeating elements among duplicates efficiently.

The key insight is to use XOR to cancel pairs and split numbers by a differing bit to isolate each unique number.