Two Non Repeating Elements in Array Using XOR in DSA Go

Mental Model

Use XOR to cancel out pairs and isolate two unique numbers by splitting the array into two groups based on a set bit.

Analogy: Imagine you have pairs of socks mixed in a drawer except two single socks. By looking at a unique thread color on one sock, you separate socks into two piles so each unique sock stands alone in its pile.

Array: [2, 3, 7, 9, 2, 3]
XOR all: 7 ⊕ 9 = 14 (binary 1110)
Split by rightmost set bit (0010):
Group 1 (bit set): 3, 7, 3 -> XOR=7
Group 2 (bit not set): 2, 9, 2 -> XOR=9
Result: unique elements separated

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

xor_all = 0 ⊕ 2 = 2 -> 2 ⊕ 3 = 1 -> 1 ⊕ 7 = 6 -> 6 ⊕ 9 = 15 -> 15 ⊕ 2 = 13 -> 13 ⊕ 3 = 14

Why: XOR cancels pairs, leaving XOR of two unique numbers (7⊕9=14)

Step 2: Find rightmost set bit in xor_all (14) to separate groups

xor_all = 1110 (binary), rightmost set bit mask = 0010 (decimal 2)

Why: This bit differs between the two unique numbers, so it helps split array

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

Group 1 (bit set): 3, 7, 3 -> XOR = 7
Group 2 (bit not set): 2, 9, 2 -> XOR = 9

Why: Pairs cancel out in each group, leaving one unique number per group

Step 4: XOR Group 1 elements again to isolate first unique number

3 ⊕ 7 = 4 -> 4 ⊕ 3 = 7

Why: Pairs cancel out, leaving the unique number 7

Step 5: XOR Group 2 elements to isolate second unique number

2 ⊕ 9 = 11 -> 11 ⊕ 2 = 9

Why: Pairs cancel out, leaving the unique number 9

Step 6: Re-examine groups to find unique numbers: 7 and 9

Unique numbers found: 7 and 9

Why: Each group contains one unique number after XOR cancellation

Result:

Unique elements: 7 and 9

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func findTwoUnique(arr []int) (int, int) {
	xorAll := 0
	// XOR all elements to get xor of two unique numbers
	for _, num := range arr {
		xorAll ^= num
	}

	// Find rightmost set bit in xorAll
	setBit := xorAll & (-xorAll)

	unique1, unique2 := 0, 0
	// Divide elements into two groups and XOR separately
	for _, num := range arr {
		if num&setBit != 0 {
			unique1 ^= num // group with set bit
		} else {
			unique2 ^= num // group without set bit
		}
	}

	return unique1, unique2
}

func main() {
	arr := []int{2, 3, 7, 9, 2, 3}
	u1, u2 := findTwoUnique(arr)
	fmt.Printf("%d -> %d -> null\n", u1, u2)
}

for _, num := range arr { xorAll ^= num }

XOR all elements to combine pairs and unique numbers

setBit := xorAll & (-xorAll)

Find rightmost set bit to separate two unique numbers

for _, num := range arr { if num&setBit != 0 { unique1 ^= num } else { unique2 ^= num } }

Split array into two groups by set bit and XOR each group to isolate unique numbers

Output

7 -> 9 -> null

Complexity Analysis

Time: O(n) because we traverse the array a constant number of times

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 and linear time

Edge Cases

Array with only two elements which are unique

Returns those two elements directly

DSA Go

for _, num := range arr {
	xorAll ^= num
}

Array with duplicates and two unique elements at start or end

Algorithm still correctly identifies unique elements

DSA Go

for _, num := range arr {
	if num&setBit != 0 {
		unique1 ^= num
	} else {
		unique2 ^= num
	}
}

Array with negative numbers

Works correctly because XOR works on bits regardless of sign

DSA Go

setBit := xorAll & (-xorAll)

When to Use This Pattern

When you need to find exactly two unique numbers in an array where all others appear twice, use XOR splitting by set bit to separate and isolate them efficiently.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly, causing wrong group separation
Fix: Use setBit := xorAll & (-xorAll) to isolate the rightmost set bit properly

Mistake: Mixing up which group to XOR, leading to incorrect unique numbers
Fix: Ensure to XOR numbers based on whether the set bit is present or not consistently

Summary

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

Use when you have exactly two non-repeating elements among pairs of duplicates.

The key insight is to use XOR to combine all elements, then split by a differing bit to isolate each unique number.

Practice

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

easy

A. XOR of all elements gives XOR of the two unique elements

B. XOR sorts the array to separate unique elements

C. XOR counts the frequency of each element

D. XOR removes duplicates by summing elements

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself.

2. Step 2: Apply XOR to all elements

   XORing all elements cancels out duplicates, leaving XOR of two unique elements.

3. Final Answer:

   XOR of all elements gives XOR of the two unique elements -> Option A

4. Quick Check:

   XOR cancels duplicates, leaving unique pair XOR [OK]

Hint: XOR all elements to isolate unique pair XOR quickly [OK]

Common Mistakes:

• Thinking XOR sorts or counts elements
• Assuming XOR gives unique elements directly
• Confusing XOR with addition or subtraction

2. Which of the following Go code snippets correctly initializes the XOR variable to start finding two non-repeating elements?

easy

A. xor := nil

B. xor := 0

C. xor := 1

D. xor := []int{}

Solution

1. Step 1: Identify correct XOR initialization

   XOR operation starts with 0 because XOR with 0 returns the number itself.

2. Step 2: Check Go syntax for variable initialization

   "xor := 0" correctly initializes an integer variable for XOR operations.

3. Final Answer:

   xor := 0 -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 to start XOR operations correctly [OK]

Common Mistakes:

• Using 1 instead of 0 for XOR start
• Trying to initialize XOR with nil or slice
• Incorrect Go syntax for variable declaration

3. What is the output of the following Go code snippet? arr := []int{2, 3, 7, 9, 2, 3, 9, 11} xor := 0 for _, v := range arr { xor ^= v } fmt.Println(xor)

medium

A. 12

B. 18

C. 0

D. 11

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, 14^9=7, 7^11=12.

2. Step 2: Verify final XOR value

   The final XOR value after processing all elements is 12.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   XOR of all elements = 12 [OK]

Hint: XOR duplicates cancel; XOR unique pair remains [OK]

Common Mistakes:

• Miscomputing XOR stepwise
• Assuming XOR sums elements
• Ignoring duplicates canceling out

4. Identify the bug in this Go code snippet that tries to find two non-repeating elements using XOR: arr := []int{4, 1, 2, 1, 2, 5} xor := 0 for i := 0; i <= len(arr); i++ { xor ^= arr[i] } fmt.Println(xor)

medium

A. Use a map instead of XOR for this problem

B. XOR variable should be initialized to 1

C. Loop condition should be i < len(arr), not i <= len(arr)

D. Array elements should be converted to strings before XOR

Solution

1. Step 1: Check loop boundary

   Loop uses i <= len(arr), which causes out-of-range error because valid indices are 0 to len(arr)-1.

2. Step 2: Correct loop condition

   Change to i < len(arr) to avoid index out of range and correctly XOR all elements.

3. Final Answer:

   Loop condition should be i < len(arr), not i <= len(arr) -> Option C

4. Quick Check:

   Index out of range fixed by correct loop boundary [OK]

Hint: Use i < len(arr) to avoid index errors in loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing XOR with wrong value
• Misunderstanding XOR usage for strings

5. Given the array arr := []int{6, 3, 5, 4, 5, 3, 4, 7}, which two numbers are the non-repeating elements found using the XOR method?

hard

A. [5, 6]

B. [3, 5]

C. [4, 7]

D. [6, 7]

Solution

1. Step 1: XOR all elements to get xorVal

   Calculate XOR: 6^3=5, 5^5=0, 0^4=4, 4^5=1, 1^3=2, 2^4=6, 6^7=1. Final xorVal = 1.

2. Step 2: Find rightmost set bit and separate elements

   Rightmost set bit in xorVal=1. Partition array into two groups based on this bit and XOR separately to find unique elements 6 and 7.

3. Final Answer:

   [6, 7] -> Option D

4. Quick Check:

   Unique elements are 6 and 7 after XOR partition [OK]

Hint: Use rightmost set bit to split and find unique elements [OK]

Common Mistakes:

• Not partitioning array by set bit
• Mixing up duplicates with unique elements
• Incorrect XOR calculations