Two Non Repeating Elements in Array Using XOR in DSA Python - 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 memory. XOR helps us compare bits and find differences between numbers. This method is faster and uses less space than checking each number one by one.

Why it matters

Without this technique, finding two unique numbers among duplicates would require extra memory or slower methods like nested loops. This would make programs slower and use more resources, especially with large data. Using XOR makes the process quick and memory-friendly, which is important in real-world applications like error detection and data analysis.

Where it fits

Before learning this, you should understand basic bitwise operations, especially XOR, and how arrays work. After this, you can explore more complex bit manipulation problems and advanced data structures that use similar tricks for optimization.

Mental Model

Core Idea

Using XOR, we can combine all numbers to isolate the two unique ones by exploiting how XOR cancels out duplicates and highlights differences.

Think of it like...

Imagine you have pairs of identical gloves mixed in a box, except two gloves have no pair. By shaking the box and feeling differences, you can separate the two unique gloves without looking at each one individually.

Array: [a, b, c, a, d, b, e, c]
Step 1: XOR all elements -> result = x = d XOR e
Step 2: Find rightmost set bit in x to divide elements into two groups
Step 3: XOR each group separately to find d and e

  ┌─────────────────────────────┐
  │ All elements XOR -> x = d⊕e │
  └─────────────┬───────────────┘
                │
      Find rightmost set bit (mask)
                │
   ┌────────────┴─────────────┐
   │                          │
Group 1 (bit set)        Group 2 (bit not set)
   │                          │
XOR elements in group    XOR elements in group
   │                          │
Result: d                 Result: e

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn how XOR works and its properties with numbers.

XOR (^) compares two bits: if bits are different, result is 1; if same, result is 0. Properties: - x ^ x = 0 (a number XOR itself is zero) - x ^ 0 = x (a number XOR zero is the number itself) - XOR is commutative and associative (order doesn't matter) Example: 5 (0101) ^ 3 (0011) = 6 (0110)

Result

XOR helps cancel out pairs of identical numbers to zero.

Understanding XOR's canceling property is key to isolating unique elements in a list.

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. Goal: Find these two unique numbers efficiently. Naive way: Check each number's count (slow and uses extra space). Better way: Use XOR to leverage bit properties.

Result

We know XOR can help find one unique number, but here we have two.

Identifying the problem constraints guides us to use XOR in a clever way.

3

Intermediate

XOR All Elements to Find Combined XOR

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

Concept: XOR all elements to get XOR of the two unique numbers combined.

XOR all array elements: duplicates cancel out to zero. Result is XOR of the two unique numbers (say x and y): x ^ y. 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

Result

We get a number representing the XOR of the two unique numbers.

Knowing the combined XOR helps us separate the two unique numbers by their differing bits.

4

Intermediate

Find Rightmost Set Bit to Separate Groups

🤔Before reading on: Do you think the rightmost set bit in XOR(x, y) is shared or different between x and y? Commit to your answer.

Concept: Use the rightmost set bit of combined XOR to divide numbers into two groups.

The rightmost set bit in x ^ y shows a bit where x and y differ. We use this bit as a mask to split array elements into two groups: - Group 1: Elements with this bit set - Group 2: Elements without this bit set Duplicates fall into the same group and cancel out. Unique numbers fall into different groups.

Result

Two groups each contain one unique number and some duplicates.

Separating numbers by a differing bit isolates unique numbers for individual XOR.

5

Intermediate

XOR Each Group to Find Unique Numbers

Concept: XOR elements in each group to find the two unique numbers separately.

XOR all elements in Group 1 -> unique number 1 XOR all elements in Group 2 -> unique number 2 Duplicates cancel out in each group. Example: Group 1: numbers with bit set -> XOR gives first unique number Group 2: numbers without bit set -> XOR gives second unique number

Result

We get the two unique numbers from the array.

This step completes the process by isolating each unique number using XOR.

6

Advanced

Implementing Complete XOR Solution in Python

🤔Before reading on: Do you think the solution requires extra memory or can be done in-place? Commit to your answer.

Concept: Write full Python code to find two unique numbers using XOR without extra space.

def two_non_repeating(arr): xor_all = 0 for num in arr: xor_all ^= num rightmost_set_bit = xor_all & (-xor_all) x = 0 y = 0 for num in arr: if num & rightmost_set_bit: x ^= num else: y ^= num return x, y Example: arr = [2, 3, 7, 9, 2, 3] print(two_non_repeating(arr)) # Output: (7, 9) or (9, 7)

Result

The function returns the two unique numbers correctly.

Knowing how to implement this efficiently in code solidifies understanding and prepares for real use.

7

Expert

Handling Edge Cases and Performance Considerations

🤔Before reading on: Do you think this XOR method works if more than two numbers are unique? Commit to your answer.

Concept: Understand limitations and how to handle special cases or large inputs.

This XOR method only works if exactly two numbers are unique and others appear twice. If more unique numbers exist, this method fails. For large arrays, this method is O(n) time and O(1) space, very efficient. Be careful with signed integers and negative numbers in some languages. In Python, negative numbers work fine with bitwise operations. For more unique numbers, other methods like hash maps are needed.

Result

You know when this method applies and when to choose alternatives.

Recognizing method limits prevents bugs and guides choosing the right tool for the problem.

Under the Hood

XOR works by comparing bits of numbers. When XORing duplicates, bits cancel out to zero because same bits XOR to zero. XORing all elements leaves XOR of unique numbers. The rightmost set bit in this XOR shows a bit where the two unique numbers differ. Using this bit, we split numbers into two groups so duplicates cancel within groups. XORing each group isolates each unique number. This works because XOR is associative and commutative, allowing grouping and cancellation.

Why designed this way?

This approach was designed to solve the problem in linear time and constant space, avoiding extra memory like hash maps. It leverages XOR's unique properties to cancel duplicates efficiently. Alternatives like sorting or counting use more time or space. The method balances speed and memory, ideal for large datasets or memory-constrained environments.

Input Array
  │
  ▼
XOR all elements -> xor_all = x ^ y
  │
  ▼
Find rightmost set bit in xor_all (mask)
  │
  ▼
Split array into two groups based on mask bit
  │               │
  ▼               ▼
Group 1 (bit set)  Group 2 (bit not set)
  │               │
XOR all elements   XOR all elements
  │               │
  ▼               ▼
Unique number x    Unique number y

Myth Busters - 3 Common Misconceptions

Quick: Does XORing all elements give you the first unique number directly? Commit yes or no.

Common Belief: XORing all elements gives one unique number directly.

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

Why it matters: Believing this causes confusion and wrong attempts to extract unique numbers without further steps.

Quick: Can this XOR method find more than two unique numbers? Commit yes or no.

Common Belief: This XOR method works for any number of unique elements.

Reality: It only works correctly if exactly two numbers are unique; otherwise, it fails.

Why it matters: Using it for more unique numbers leads to incorrect results and wasted debugging time.

Quick: Does the order of XOR operations affect the result? Commit yes or no.

Common Belief: The order of XOR operations changes the final result.

Reality: XOR is commutative and associative; order does not affect the result.

Why it matters: Misunderstanding this can cause unnecessary complexity or incorrect assumptions in code.

Expert Zone

1

The choice of rightmost set bit is arbitrary; any set bit in xor_all can be used to split groups.

2

In some languages, handling negative numbers with bitwise operations requires care due to two's complement representation.

3

This method assumes exactly two unique numbers; detecting this condition beforehand can prevent misuse.

When NOT to use

Do not use this method if more than two unique numbers exist or if duplicates appear more than twice. Instead, use hash maps or sorting-based methods for those cases.

Production Patterns

Used in embedded systems and performance-critical code where memory is limited. Also common in coding interviews to test bit manipulation skills and problem-solving efficiency.

Connections

Bitwise Operations

Builds-on

Mastering XOR here deepens understanding of bitwise operations, which are fundamental in low-level programming and optimization.

Hash Maps

Alternative approach

Knowing XOR method helps appreciate when hash maps are needed and why XOR is more memory efficient for specific problems.

Error Detection in Communication

Similar pattern

XOR is used in error detection codes like parity bits; understanding this problem reveals how XOR detects differences and errors in data.

Common Pitfalls

#1 Trying to find unique numbers by XORing all elements and returning the result directly.

Wrong approach:

def find_unique(arr):
result = 0
for num in arr:
result ^= num
return result # Incorrect for two unique numbers

Correct approach:

def find_two_unique(arr):
xor_all = 0
for num in arr:
xor_all ^= num
rightmost_set_bit = xor_all & (-xor_all)
x = 0
y = 0
for num in arr:
if num & rightmost_set_bit:
x ^= num
else:
y ^= num
return x, y

Root cause:

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

#2 Using this XOR method when more than two unique numbers exist in the array.

Wrong approach:

arr = [1, 2, 3, 2, 1, 4]
# Using XOR method expecting to find unique numbers
# But there are three unique numbers: 3, 4, and possibly others

Correct approach:

Use a hash map or frequency count to find all unique numbers when more than two exist.

Root cause:

Assuming the XOR method generalizes beyond two unique numbers without verifying problem constraints.

#3 Not handling negative numbers correctly in languages with signed integers and bitwise operations.

Wrong approach:

Using bitwise operations without considering two's complement representation, leading to wrong mask calculation.

Correct approach:

In Python, negative numbers work fine; in other languages, use unsigned types or careful masking.

Root cause:

Lack of understanding of how negative numbers are represented and handled in bitwise operations.

Key Takeaways

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

Finding the rightmost set bit in combined XOR helps separate two unique numbers into distinct groups.

XORing each group isolates the unique numbers efficiently without extra memory.

This method only works when exactly two numbers are unique and others appear twice.

Understanding bitwise operations and problem constraints is essential to apply this technique correctly.