Two Non Repeating Elements in Array Using XOR in DSA Go - Deep Dive

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

This topic teaches how to find two unique numbers in an array where every other number repeats exactly twice. We use a special operation called XOR to do this efficiently without extra space. The method helps identify these two numbers quickly by using properties of XOR. This is useful when you want to find outliers in data without sorting or extra memory.

Why it matters

Without this method, finding two unique numbers among duplicates would require extra memory or slower sorting methods. This XOR approach solves the problem in linear time and constant space, making programs faster and more memory-efficient. It is important in real-world tasks like error detection, data analysis, and security where quick identification of unique elements matters.

Where it fits

Before learning this, you should understand basic arrays and the XOR operation. After this, you can explore similar problems like finding a single unique element or using bit manipulation for other tasks. This topic fits into the broader study of bitwise operations and efficient data processing.

Mental Model

Core Idea

Using XOR properties, we can isolate two unique numbers in a list where all others appear twice by separating numbers based on differing bits.

Think of it like...

Imagine you have a box of pairs of socks, but two socks are unique and don't have a pair. By looking at a specific color stripe on the socks, you can split the socks into two groups so that each unique sock ends up in a different group, making it easy to find them.

Array: [a, b, c, d, ..., x, y]
Step 1: XOR all elements -> xor = x ^ y (unique elements)
Step 2: Find rightmost set bit in xor -> mask
Step 3: Divide elements into two groups based on mask bit:
  Group 1: bits set
  Group 2: bits not set
Step 4: XOR each group separately -> unique elements found

Diagram:
  ┌───────────────┐
  │ Full Array    │
  └──────┬────────┘
         │ XOR all elements
         ▼
      xor = x ^ y
         │
         ▼
  Find rightmost set bit (mask)
         │
         ▼
  ┌───────────────┐      ┌───────────────┐
  │ Group 1 (bit=1)│      │ Group 2 (bit=0)│
  └──────┬────────┘      └──────┬────────┘
         │                     │
         ▼                     ▼
  XOR elements in group 1   XOR elements in group 2
         │                     │
         ▼                     ▼
       unique1               unique2

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does and its key properties.

XOR (exclusive OR) compares two bits and returns 1 if they are different, 0 if they are the same. For example, 0 XOR 0 = 0, 1 XOR 0 = 1, 1 XOR 1 = 0. Important properties: - x XOR x = 0 (a number XOR itself is zero) - x XOR 0 = x (a number XOR zero is the number itself) - XOR is commutative and associative (order doesn't matter) Example: 5 (0101) XOR 3 (0011) = 6 (0110)

Result

Knowing XOR properties lets you combine numbers and cancel duplicates.

Understanding XOR's canceling effect is key to isolating unique elements in arrays.

2

Foundation

Problem Setup: Array with Two Unique Numbers

Concept: Recognize the problem where all numbers repeat twice except two unique ones.

Given an array like [2, 3, 7, 9, 2, 3], numbers 7 and 9 appear once, others twice. The goal is to find these two unique numbers efficiently. Naive ways include using extra memory (hash maps) or sorting, but these are less efficient.

Result

Clear problem understanding: find two unique numbers among duplicates.

Framing the problem helps appreciate why XOR-based solutions are elegant and efficient.

3

Intermediate

XOR All Elements to Get Combined XOR

🤔Before reading on: do you think XORing all elements gives one unique number or a combination? Commit to your answer.

Concept: XORing all elements cancels duplicates, leaving XOR of the two unique numbers.

If you XOR all elements in the array, pairs cancel out because x XOR x = 0. What remains is xor = unique1 XOR unique2. Example: Array: [2, 3, 7, 9, 2, 3] XOR all: 2^3^7^9^2^3 = (2^2)^(3^3)^7^9 = 0^0^7^9 = 7^9 This xor is not one unique number but a combination of both.

Result

xor holds bits where the two unique numbers differ.

Knowing that XOR of all elements isolates combined difference is the foundation for splitting the problem.

4

Intermediate

Find Rightmost Set Bit to Separate Groups

🤔Before reading on: do you think any set bit in xor can be used to separate numbers? Commit to your answer.

Concept: Use the rightmost set bit in xor to divide numbers into two groups differing at that bit.

The rightmost set bit in xor indicates a bit where unique1 and unique2 differ. We find this bit by: mask = xor & (-xor) This mask helps split the array into two groups: - Group 1: numbers with this bit set - Group 2: numbers without this bit set Each group contains one unique number and pairs that cancel out.

Result

Two groups formed, each with one unique number.

Using the rightmost set bit cleverly partitions numbers to isolate unique elements.

5

Intermediate

XOR Each Group to Find Unique Numbers

Concept: XORing each group separately reveals the two unique numbers.

After splitting, XOR all numbers in Group 1 to get unique1. XOR all numbers in Group 2 to get unique2. Pairs cancel out in each group, leaving only the unique number. Example: Group 1: [7, 2, 2] XOR: 7 ^ 2 ^ 2 = 7 Group 2: [9, 3, 3] XOR: 9 ^ 3 ^ 3 = 9

Result

unique1 and unique2 found correctly.

Separating and XORing groups isolates unique numbers without extra memory.

6

Advanced

Implementing in Go with Bitwise Operations

🤔Before reading on: do you think the Go code needs loops or recursion to find unique numbers? Commit to your answer.

Concept: Translate the XOR logic into efficient Go code using loops and bitwise operators.

Go code example: package main import "fmt" func findTwoUnique(arr []int) (int, int) { xor := 0 for _, num := range arr { xor ^= num } mask := xor & (-xor) x, y := 0, 0 for _, num := range arr { if num&mask != 0 { x ^= num } else { y ^= num } } return x, y } func main() { arr := []int{2, 3, 7, 9, 2, 3} a, b := findTwoUnique(arr) fmt.Printf("Two unique numbers are: %d and %d\n", a, b) }

Result

Output: Two unique numbers are: 7 and 9

Implementing bitwise logic in Go shows practical application and efficiency.

7

Expert

Handling Negative Numbers and Edge Cases

🤔Before reading on: do you think this XOR method works with negative numbers as is? Commit to your answer.

Concept: Understand how two's complement and negative numbers affect XOR and mask calculation.

XOR works with negative numbers because Go uses two's complement representation. The mask calculation mask = xor & (-xor) relies on two's complement to isolate rightmost set bit. Edge cases: - If array length is less than 2, method fails. - If unique numbers are the same (invalid input), result is zero. Testing with negative numbers: arr := []int{-1, -2, -1, -3} Unique numbers: -2 and -3 Method still works correctly.

Result

Method robust for negative numbers and typical edge cases.

Knowing two's complement ensures confidence in XOR method across all integer values.

Under the Hood

XOR operation compares bits of numbers. When XORing all array elements, pairs cancel out because identical bits XOR to zero. The result is XOR of the two unique numbers, which differ in at least one bit. Finding the rightmost set bit in this XOR result identifies a bit where these two numbers differ. Splitting the array based on this bit groups numbers so that each unique number is isolated with pairs that cancel out. XORing each group then reveals the unique numbers.

Why designed this way?

This method was designed to solve the problem in linear time and constant space, avoiding extra memory or sorting. XOR's properties make it ideal for canceling duplicates. Using the rightmost set bit to split groups is a clever trick to separate two unique numbers without confusion. Alternatives like hash maps use extra space, and sorting changes order and costs more time.

Full Array
   │
   ▼
XOR all elements
   │
   ▼
xor = unique1 XOR unique2
   │
   ▼
Find rightmost set bit (mask)
   │
   ▼
Split array into two groups based on mask bit
   ├───────────────┬───────────────┤
   │               │               │
Group 1 (bit=1)  Group 2 (bit=0)  
   │               │               
   ▼               ▼               
XOR group 1       XOR group 2     
   │               │               
   ▼               ▼               
unique1           unique2

Myth Busters - 4 Common Misconceptions

Quick: Does XORing all elements give one unique number or a combination of two? Commit to your answer.

Common Belief: XORing all elements will give one unique number directly.

Reality: XORing all elements gives the XOR of the two unique numbers combined, not a single unique number.

Why it matters: Believing this causes confusion and incorrect attempts to extract unique numbers without splitting groups.

Quick: Can any set bit in xor be used to split groups equally? Commit to yes or no.

Common Belief: Any set bit in the combined XOR can be used to separate the two unique numbers.

Reality: Only bits where the two unique numbers differ can be used; the rightmost set bit is a simple choice but any differing bit works.

Why it matters: Choosing a wrong bit may fail to separate unique numbers properly, leading to incorrect results.

Quick: Does this method require extra memory like hash maps? Commit to yes or no.

Common Belief: This method needs extra memory to track counts or store elements.

Reality: This XOR method uses constant extra space, only a few variables, no additional data structures.

Why it matters: Misunderstanding this leads to ignoring this efficient approach in favor of slower, memory-heavy methods.

Quick: Does this method fail with negative numbers? Commit to yes or no.

Common Belief: XOR and mask calculations don't work correctly with negative numbers.

Reality: XOR and mask calculations work correctly with negative numbers due to two's complement representation.

Why it matters: Avoiding this method for negative numbers limits its usefulness unnecessarily.

Expert Zone

1

The choice of rightmost set bit is a simple heuristic; any differing bit between the two unique numbers can be used to split groups.

2

Two's complement representation ensures that mask = xor & (-xor) isolates the rightmost set bit even for negative numbers.

3

The method assumes exactly two unique numbers; if input violates this, results are unpredictable.

When NOT to use

Avoid this method if there are more than two unique numbers or if duplicates appear more than twice. For multiple unique elements, use hash maps or sorting. For single unique number, simpler XOR methods suffice.

Production Patterns

Used in embedded systems and performance-critical code where memory is limited. Also common in coding interviews to test bitwise manipulation skills. Variants appear in error detection and cryptography for identifying anomalies.

Connections

Single Unique Element Using XOR

Builds-on

Understanding how XOR cancels duplicates in the single unique element problem helps grasp the two unique elements extension.

Bit Manipulation Techniques

Same pattern

This problem is a classic example of using bitwise operations to solve array problems efficiently.

Signal Processing - Noise Filtering

Analogous pattern

Separating unique signals from repeated noise in signal processing uses similar principles of isolating differences, showing cross-domain relevance.

Common Pitfalls

#1 Using XOR of all elements as one unique number directly.

Wrong approach:

xor := 0
for _, num := range arr {
xor ^= num
}
fmt.Println("Unique number is", xor) // Incorrect for two unique numbers

Correct approach:

xor := 0
for _, num := range arr {
xor ^= num
}
mask := xor & (-xor)
x, y := 0, 0
for _, num := range arr {
if num&mask != 0 {
x ^= num
} else {
y ^= num
}
}
fmt.Println("Unique numbers are", x, y)

Root cause:

Misunderstanding that XOR of all elements with two unique numbers is a combined XOR, not a single unique number.

#2 Choosing a mask bit that is zero in xor to split groups.

Wrong approach:

mask := 1 << 5 // arbitrary bit
// mask might be zero in xor
// splitting groups using mask leads to wrong grouping

Correct approach:

mask := xor & (-xor) // rightmost set bit ensures correct split

Root cause:

Not ensuring the mask corresponds to a set bit in xor causes incorrect group division.

#3 Assuming method works if duplicates appear more than twice.

Wrong approach:

arr := []int{2, 2, 2, 3, 3, 7, 9}
// Using XOR method expecting unique numbers 7 and 9

Correct approach:

Use hash maps or sorting when duplicates appear more than twice; XOR method only works for exactly two unique numbers and pairs.

Root cause:

Method relies on pairs canceling out; more than two duplicates break this assumption.

Key Takeaways

XOR operation cancels out pairs of identical numbers, leaving XOR of unique elements.

Finding the rightmost set bit in the combined XOR helps split numbers into two groups to isolate unique elements.

XORing each group separately reveals the two unique numbers efficiently without extra memory.

This method works for negative numbers due to two's complement representation.

It only works when exactly two unique numbers exist and all others appear exactly twice.

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