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

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

Given an array where every element appears exactly twice except for two elements which appear once, find those two unique elements. The XOR-based solution achieves O(n) time and O(1) space by exploiting XOR properties: a ^ a = 0, a ^ 0 = a, and the fact that XOR of all elements gives xor of the two unique elements.

Why it matters

This problem demonstrates advanced bit manipulation — specifically using a single differing bit to partition elements into two groups. It is a direct extension of the 'one non-repeating element' problem and appears frequently in bit manipulation interview rounds. In Rust, the ^ operator works identically to other languages but Rust's type system ensures no integer overflow surprises.

Where it fits

You need to understand XOR properties (a^a=0, a^0=a) and the 'find one non-repeating element' solution before tackling this. After mastering it, finding the missing number, detecting single corrupt elements, and Gray code generation follow naturally.

Mental Model

Core Idea

XOR all elements to get x = a ^ b (the two unique numbers). Find any bit where a and b differ (a set bit in x). Use that bit to partition all elements into two groups — each group XORs to one of the unique numbers.

Think of it like...

Imagine two groups of identical pairs plus two solo cards. Shuffle everything and XOR all cards together — the pairs cancel out, leaving the XOR of the two solos. Now find any feature that distinguishes the two solos (one bit where they differ). Use that feature to sort all cards into two piles — each pile's XOR gives one solo card.

Array: [1, 2, 3, 2, 1, 4]  →  two unique: 3 and 4

Step 1: XOR all → 1^2^3^2^1^4 = 3^4 = 0b011^0b100 = 0b111 = 7

Step 2: Find rightmost set bit of 7 → bit 0 (value 1)

Step 3: Partition by bit 0:
  Bit 0 SET:   [1, 3, 1]  → XOR = 3 ✓
  Bit 0 CLEAR: [2, 2, 4]  → XOR = 4 ✓

Build-Up - 5 Steps

1

Foundation

XOR Properties Recap

Concept: a ^ a = 0, a ^ 0 = a, XOR is commutative and associative.

XOR cancels identical pairs: 2^2=0, 5^5=0. XOR with zero is identity: 3^0=3. Order doesn't matter: 1^2^1 = 2^1^1 = 2. These three properties mean: XOR all elements in array → all pairs cancel → only non-repeating elements remain XORed together.

Result

XOR of all elements = a ^ b where a and b are the two unique elements.

XOR is the perfect tool for finding unique elements because pairs cancel to 0 — no information about their values is needed.

2

Foundation

Step 1 — XOR All Elements

Concept: XOR the entire array to get xor_ab = a ^ b.

In Rust: let xor_ab = nums.iter().fold(0i32, |acc, &x| acc ^ x). Result is xor_ab = a ^ b. Since a != b, xor_ab != 0 — at least one bit differs between a and b. We cannot determine a and b individually yet — xor_ab only tells us where they differ.

Result

xor_ab holds the XOR of the two unique elements.

fold with XOR is clean Rust — the iterator approach is idiomatic and avoids explicit loops.

3

Intermediate

Step 2 — Find a Differing Bit

🤔Before reading on: given xor_ab = 7 (binary 111), which bit should we use to partition elements? Does the choice matter? Commit to your answer.

Concept: Extract any set bit from xor_ab — any bit where a and b differ works as a partition criterion.

The rightmost set bit is easiest to extract: set_bit = xor_ab & (-xor_ab) or equivalently xor_ab & (xor_ab.wrapping_neg()). In Rust: let set_bit = xor_ab & xor_ab.wrapping_neg(). This isolates the lowest set bit. Example: xor_ab=6 (110) → set_bit=2 (010). Any set bit works — we choose lowest for simplicity.

Result

set_bit is a power of 2 with exactly one bit set — the partition key.

x & (-x) isolates the rightmost set bit in O(1). In Rust use wrapping_neg() to avoid overflow on i32::MIN — or use i32::leading_zeros() and bit shifting.

4

Intermediate

Step 3 — Partition and XOR Each Group

🤔Before reading on: why does partitioning by one bit separate a and b into different groups? Commit to your answer.

Concept: Elements with set_bit set go to group A, others to group B. a is in one group, b in the other.

Since set_bit is a bit where a and b differ, exactly one of them has that bit set. All elements with the bit set go to group A — their pairs cancel in XOR. What remains is either a or b. Similarly for group B. In Rust: let (mut g1, mut g2) = (0i32, 0i32); for &x in nums { if x & set_bit != 0 { g1 ^= x; } else { g2 ^= x; } }. g1 and g2 are the two unique elements.

Result

(g1, g2) contains the two unique elements in O(n) with O(1) space.

Pairs in each group cancel via XOR regardless of which group they're in — because both copies of any repeated element end up in the same group (they have the same bit value at set_bit position).

5

Advanced

Rust-Specific: Handling Signed Integers and Wrapping

🤔Before reading on: why might xor_ab.wrapping_neg() be needed in Rust instead of -xor_ab? Commit to your answer.

Concept: In Rust, integer overflow in debug mode panics. Use wrapping arithmetic explicitly for bit manipulation.

xor_ab & (-xor_ab) in C or Python works on signed integers. In Rust debug mode, negating i32::MIN overflows and panics. Use xor_ab.wrapping_neg() or cast to u32: let set_bit = (xor_ab as u32) & (xor_ab.wrapping_neg() as u32). Alternatively, use trailing_zeros(): let set_bit = 1u32 << xor_ab.trailing_zeros(). This is cleaner and avoids signed arithmetic entirely.

Result

Rust-safe bit isolation using trailing_zeros() or wrapping_neg().

Rust's debug mode overflow panics are a feature — they catch bugs. Use wrapping_*/checked_* or cast to unsigned when intentionally using two's complement arithmetic.

Under the Hood

XOR cancellation works because XOR is its own inverse: a^a=0 for any a. The partition step works because: (1) all repeated elements have both their copies in the same group (same bit value), so they cancel in that group's XOR; (2) the two unique elements are in different groups (they differ at set_bit), so each group's XOR yields exactly one unique element. Total: two passes over the array, O(n) time, O(1) space.

Why designed this way?

The challenge of the 'two unique elements' variant (vs one unique) is that XOR of all elements gives a ^ b, not a or b individually. The partitioning step is the key insight: use any bit where a and b differ to create two independent 'find one unique' subproblems, each solvable with simple XOR.

Example: [3, 4, 1, 2, 4, 1, 3, 5] → unique are 2 and 5

XOR all: 3^4^1^2^4^1^3^5 = 2^5 = 010^101 = 111 = 7
set_bit = 7 & (-7) = 1 (bit 0)

Partition by bit 0:
  Bit 0 SET (odd):  [3,1,1,3,5] → 3^1^1^3^5 = 5 ✓
  Bit 0 CLEAR(even):[4,2,4]     → 4^2^4 = 2 ✓

Result: (5, 2) ✓

Myth Busters - 2 Common Misconceptions

Quick: does the choice of which set bit to use affect correctness? Commit yes or no.

Common Belief: We must use a specific bit (like the highest or lowest) for the partition to work.

Reality: Any set bit in xor_ab works. All set bits represent positions where a and b differ. Any such position correctly separates a and b into different groups.

Why it matters: Understanding that any set bit works simplifies the implementation — always use the lowest set bit (xor_ab & -xor_ab) for simplicity.

Quick: do repeated elements always end up in the same partition group? Commit yes or no.

Common Belief: Repeated elements might split between groups, preventing pair cancellation.

Reality: Repeated elements are always in the same group — both copies have the same value, so they have the same bit at set_bit position. They always end up in the same group and always cancel via XOR.

Why it matters: This is the correctness guarantee. If repeated elements could split, the approach would fail. They can't split because identical values always map to the same group.

Expert Zone

1

This technique extends to 'find three unique elements' but requires two partitioning steps and gets significantly more complex.

2

trailing_zeros() on 0 in Rust returns 32 for u32 and 64 for u64 — always check xor_ab != 0 before calling, which is guaranteed since a != b.

3

For very large arrays in Rust, consider using iter().fold() over a for loop for idiomatic, potentially SIMD-optimizable XOR aggregation.

When NOT to use

If you need to return the elements in a specific order or handle more than two unique elements, use a HashMap frequency counter instead — O(n) time, O(k) space where k is the number of unique elements.

Production Patterns

XOR-based unique element detection appears in: error correction codes (detecting bit flip positions), cryptographic checksums, network packet integrity, and hardware parity bit computation. The partition technique appears in Quicksort's partition step and Dutch National Flag partitioning.

Connections

Find Single Non-Repeating Element

The 'two unique elements' problem is a direct extension — XOR all gives the answer for one unique, XOR+partition gives both for two unique.

Mastering the single-unique XOR solution is the prerequisite. This problem adds one step: using a differing bit to split into two independent single-unique subproblems.

Bit Manipulation — Isolating Rightmost Set Bit

x & (-x) or x.trailing_zeros() both isolate the rightmost set bit — a fundamental bit trick used in Binary Indexed Trees, segment trees, and bit manipulation problems.

The rightmost-set-bit isolation technique (x & -x) appears across many bit manipulation problems. Recognizing it as a building block speeds up solving other bit problems.

Common Pitfalls

#1 Using -xor_ab in Rust without wrapping, causing panic on i32::MIN.

Wrong approach:

let set_bit = xor_ab & (-xor_ab); // PANIC in debug if xor_ab == i32::MIN

Correct approach:

let set_bit = xor_ab & xor_ab.wrapping_neg(); // Safe
// Or cleaner:
let shift = xor_ab.trailing_zeros();
let set_bit = 1i32 << shift;

Root cause:

Rust debug mode panics on signed integer overflow. i32::MIN.wrapping_neg() correctly returns i32::MIN (since -MIN overflows back to MIN in two's complement).

#2 XOR-ing into a signed integer accumulator without considering bit width.

Wrong approach:

let mut xor: i8 = 0; // WRONG: i8 may overflow XOR of large values
for &x in &nums { xor ^= x as i8; }

Correct approach:

let mut xor: i32 = 0; // Match the element type
for &x in &nums { xor ^= x; }
// Or idiomatically:
let xor = nums.iter().fold(0i32, |acc, &x| acc ^ x);

Root cause:

XOR never overflows (it's a bitwise operation), but casting to a smaller type (i8) before XOR can cause information loss if elements are larger than i8::MAX.

Key Takeaways

XOR all elements gives a ^ b (pairs cancel). Find any set bit in this result to partition elements — the two unique numbers differ at that bit.

All repeated elements always land in the same partition group (same bit value) and cancel. The two unique elements land in different groups.

Use xor_ab.trailing_zeros() in Rust for safe rightmost-set-bit isolation — avoids the overflow risk of xor_ab & (-xor_ab) with signed integers.

Time O(n), Space O(1) — two passes: one to XOR all, one to partition and XOR each group.

Any set bit in xor_ab works for partitioning — the choice doesn't affect correctness, only which element appears in which group.

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 removes duplicates by summing elements

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

C. XOR sorts the array to find unique elements

D. XOR counts the frequency of elements

Solution

1. Step 1: Understand XOR operation on array elements

   XORing all elements cancels out pairs of repeating elements because x ^ x = 0.

2. Step 2: Result after XORing all elements

   The result is XOR of the two unique elements since all duplicates cancel out.

3. Final Answer:

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

4. Quick Check:

   XOR cancels duplicates = XOR of unique elements [OK]

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

Common Mistakes:

• Thinking XOR counts frequency
• Assuming XOR sorts elements
• Using XOR as sum instead of bitwise operation

2. Which Rust syntax correctly initializes a variable to store XOR of all elements in a vector named arr?

easy

A. let mut xor = 0; for &num in &arr { xor ^= num; }

B. let xor = arr.reduce(|a, b| a + b);

C. let xor = arr.iter().sum();

D. let mut xor = 1; for num in arr { xor *= num; }

Solution

1. Step 1: Initialize mutable variable for XOR

   Use let mut xor = 0; to start XOR from zero.

2. Step 2: Iterate over references to elements and XOR

   Use for &num in &arr { xor ^= num; } to XOR each element.

3. Final Answer:

   let mut xor = 0; for &num in &arr { xor ^= num; } -> Option A

4. Quick Check:

   Mutable xor with ^= in loop = correct syntax [OK]

Hint: Use 'let mut xor = 0;' and XOR in loop [OK]

Common Mistakes:

• Using sum() instead of XOR
• Trying to multiply elements
• Not using mutable variable for XOR

3. What is the output of the following Rust code snippet?

let arr = vec![2, 3, 7, 9, 2, 3];
let mut xor = 0;
for &num in &arr {
    xor ^= num;
}
println!("{}", xor);

medium

A. 16

B. 0

C. 14

D. 9

Solution

1. Step 1: XOR all elements in the array

   Calculate 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 step-by-step: 2 ^ 3 = 1, 1 ^ 7 = 6, 6 ^ 9 = 15, 15 ^ 2 = 13, 13 ^ 3 = 14.

2. Step 2: Final XOR value

   The final XOR value is 14 after processing all elements.

3. Final Answer:

   14 -> Option C

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR duplicates cancel, result is XOR of unique elements [OK]

Common Mistakes:

• Incorrect XOR calculation order
• Assuming sum instead of XOR
• Forgetting XOR cancels duplicates

4. Identify the error in this Rust code snippet that tries to find two unique elements using XOR:

let arr = vec![4, 1, 2, 1, 2, 5];
let mut xor = 0;
for num in arr {
    xor ^= num;
}
let set_bit = xor & (-xor);
println!("{}", set_bit);

medium

A. Incorrect loop syntax for vector iteration

B. Missing mutable keyword for xor variable

C. Cannot use negative sign on unsigned integer

D. No error, code runs fine

Solution

1. Step 1: Understand variable types and operations

   In Rust, integer literals default to i32 (signed), so xor & (-xor) is valid.

2. Step 2: Verify code execution

   Loop correctly computes XOR (1), set_bit calculates correctly (1). No syntax or runtime errors.

3. Final Answer:

   No error, code runs fine -> Option D

4. Quick Check:

   i32 supports unary minus operator [OK]

Hint: Rust ints default to signed i32, -xor valid [OK]

Common Mistakes:

• Misassuming unsigned integers by default
• Thinking 'for num in arr' syntax is wrong
• Expecting mutable keyword issues

5. Given an array arr = [6, 1, 3, 6, 1, 5], which Rust code snippet correctly finds the two non-repeating elements using XOR?

hard

A. let mut xor = 0;
for &num in &arr { xor ^= num; }
let set_bit = xor & xor.wrapping_neg();
let (mut x, mut y) = (0, 0);
for &num in &arr {
if num & set_bit != 0 { x ^= num; } else { y ^= num; }
}
println!("{} {}", x, y);

B. let mut xor = 0;
for num in arr {
xor += num;
}
println!("{}", xor);

C. let mut xor = 0;
for &num in &arr {
xor ^= num;
}
println!("{}", xor);

D. let mut xor = 0;
for &num in &arr {
xor *= num;
}
println!("{}", xor);

Solution

1. Step 1: XOR all elements to get xor of two unique numbers

   Loop over array and XOR all elements to get xor = 6 ^ 1 ^ 3 ^ 6 ^ 1 ^ 5 = 3 ^ 5 = 6.

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

   Calculate set_bit = xor & xor.wrapping_neg() to isolate differing bit. Then separate elements into two groups based on this bit and XOR each group to find unique elements.

3. Step 3: Print the two unique elements

   After separation and XOR, x and y hold the two unique numbers 3 and 5.

4. Final Answer:

   Code snippet in Option A correctly finds two unique elements -> Option A

5. Quick Check:

   Use XOR, set bit, separate groups = correct approach [OK]

Hint: Use XOR, find set bit, separate and XOR groups [OK]

Common Mistakes:

• Using sum or multiplication instead of XOR
• Not isolating rightmost set bit correctly
• Not separating elements into two groups