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.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where every other element repeats twice?

easy

A. To sort the array in ascending order

B. To count the frequency of each element

C. To cancel out all repeating elements and isolate the XOR of the two unique elements

D. To reverse the array elements

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself. This helps cancel out repeating elements.

2. Step 2: Apply XOR on all elements

   When XOR is applied on the entire array, all repeating elements cancel out, leaving XOR of the two unique elements.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option C

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR duplicates become zero, leaving unique elements XOR [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Using XOR to count frequencies
• Assuming XOR reverses elements

2. Which of the following Python code snippets correctly initializes the XOR of all elements in a list named arr to zero before processing?

easy

A. xor = 1

B. xor = 0

C. xor = arr[0]

D. xor = None

Solution

1. Step 1: Initialize XOR variable

   We start XOR with 0 because XOR with 0 returns the other number unchanged.

2. Step 2: Confirm initialization correctness

   Starting with 0 ensures the first XOR operation correctly sets the value to the first element.

3. Final Answer:

   xor = 0 -> Option B

4. Quick Check:

   Initialize XOR with 0 for correct accumulation [OK]

Hint: Start XOR with 0 to accumulate correctly [OK]

Common Mistakes:

• Initializing XOR with 1 causes wrong results
• Using first element without XOR 0 initialization
• Setting XOR to None causes errors

3. What will be the output of the following Python code?

arr = [2, 3, 7, 9, 2, 3]
xor = 0
for num in arr:
    xor ^= num
print(xor)

medium

A. 0

B. 9

C. 7

D. 14

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Final XOR value

   The final XOR after processing all elements is 14.

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Stepwise XOR = 14 [OK]

Hint: XOR all elements stepwise to find combined XOR [OK]

Common Mistakes:

• Forgetting XOR is cumulative and order matters
• Mistaking XOR with addition
• Stopping XOR early

4. Identify the error in the following code snippet that attempts to find two non-repeating elements using XOR:

arr = [4, 1, 2, 1, 2, 5]
xor = 0
for num in arr:
    xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
    if (num & set_bit) > 0:
        num1 ^= num
    else:
        num2 ^= num
print(num1, num2)

medium

A. No error, code works correctly

B. XOR initialization should be arr[0] instead of 0

C. Incorrect calculation of set_bit using bitwise NOT

D. Using > 0 instead of != 0 in if condition

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly isolates rightmost set bit.

2. Step 2: Verify partition and XOR groups

   Elements are split by set_bit and XORed separately to find unique elements.

3. Step 3: Confirm output correctness

   Code correctly prints the two unique numbers without errors.

4. Final Answer:

   No error, code works correctly -> Option A

5. Quick Check:

   Correct set_bit and partitioning = code works [OK]

Hint: Use xor & ~(xor-1) to find rightmost set bit correctly [OK]

Common Mistakes:

• Misusing bitwise NOT causing wrong set_bit
• Initializing XOR incorrectly
• Using wrong condition in if statement

5. Given an array arr = [10, 20, 10, 30, 40, 20], which of the following Python code snippets correctly finds the two non-repeating elements using XOR and prints them in ascending order?

hard

A. xor = 0
for num in arr:
xor ^= num
set_bit = xor & (-xor)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

B. xor = 0
for num in arr:
xor ^= num
set_bit = xor | (xor - 1)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

C. xor = arr[0]
for num in arr[1:]:
xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) == 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

D. xor = 0
for num in arr:
xor ^= num
set_bit = xor & ~(xor + 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) != 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

Solution

1. Step 1: Calculate XOR of all elements

   xor accumulates XOR of all elements, isolating XOR of two unique numbers.

2. Step 2: Find rightmost set bit correctly

   set_bit = xor & (-xor) correctly isolates the rightmost set bit for partitioning.

3. Step 3: Partition elements and XOR separately

   Elements are split by set_bit and XORed to find the two unique numbers.

4. Step 4: Sort and print unique elements

   Sorting ensures output is in ascending order as required.

5. Final Answer:

   Code in option A correctly finds and prints [30, 40] -> Option A

6. Quick Check:

   Rightmost set bit with xor & (-xor) + partition = correct [OK]

Hint: Use xor & (-xor) to find set bit and partition array [OK]

Common Mistakes:

• Using incorrect set_bit calculation like xor | (xor - 1)
• Wrong initialization of xor variable
• Incorrect condition in partition if statement