Two Non Repeating Elements in Array Using XOR in DSA Rust

Mental Model

Use XOR to cancel out pairs and find 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 socks don't have a pair. By shaking the drawer and separating socks by a unique feature (like color), you find the two unmatched socks.

Array: [2, 3, 7, 9, 2, 3]
Unique elements: 7 and 9
XOR all elements -> xor = 14
Find rightmost set bit in xor -> mask = 2 (binary 0010)
Split array into two groups by mask bit
Group 1: elements with bit set [2, 3, 7, 2, 3]
Group 2: elements without bit set [9]
XOR each group separately to find unique elements: 7 and 9

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 = 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3

xor = 0 -> 2 -> 1 -> 6 -> 15 -> 13 -> 14

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

Step 2: Find rightmost set bit in xor (14) -> mask = 2 (binary 0010)

mask = 2

Why: This bit differs between the two unique numbers, used to separate them

Step 3: Divide array into two groups by mask bit: group1 with bit set, group2 without

group1: [2, 3, 7, 2, 3] (bit set)
group2: [9] (bit not set)

Why: Unique numbers fall into different groups because they differ at mask bit

Step 4: XOR elements in group1: 2 ^ 3 ^ 7 ^ 2 ^ 3 = 7

group1_xor = 7

Why: Pairs cancel out (2 ^ 2 = 0, 3 ^ 3 = 0), leaving unique 7

Step 5: XOR elements in group2: 9 = 9

group2_xor = 9

Why: Only unique 9 in this group

Step 6: Final unique numbers are 7 and 9

unique elements: 7, 9

Why: Each group's XOR yields one unique number

Result:

Unique elements: 7 and 9

Annotated Code

DSA Rust

fn find_two_non_repeating(arr: &[i32]) -> (i32, i32) {
    let mut xor_all = 0;
    for &num in arr {
        xor_all ^= num; // XOR all elements to get xor of two unique numbers
    }

    // Find rightmost set bit in xor_all
    let mask = xor_all & (-xor_all);

    let mut x = 0;
    let mut y = 0;

    for &num in arr {
        if num & mask != 0 {
            x ^= num; // XOR group with set bit
        } else {
            y ^= num; // XOR group without set bit
        }
    }

    (x, y)
}

fn main() {
    let arr = [2, 3, 7, 9, 2, 3];
    let (num1, num2) = find_two_non_repeating(&arr);
    println!("{} {}", num1, num2);
}

xor_all ^= num; // XOR all elements to get xor of two unique numbers

XOR all elements to cancel pairs and get xor of unique numbers

let mask = xor_all & (-xor_all);

Find rightmost set bit to separate unique numbers

if num & mask != 0 { x ^= num; } else { y ^= num; }

Divide elements into two groups and XOR separately to find unique numbers

Output

7 9

Complexity Analysis

Time: O(n) because we traverse the array a few times linearly

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Better than using hash maps which use O(n) space; XOR uses constant space and linear time

Edge Cases

Array with only two elements, both unique

Returns the two elements correctly

DSA Rust

xor_all ^= num; // XOR all elements to get xor of two unique numbers

Array with duplicates but only two unique elements

Duplicates cancel out, unique elements found

DSA Rust

if num & mask != 0 { x ^= num; } else { y ^= num; }

Array with negative numbers

Works correctly because XOR works on bits regardless of sign

DSA Rust

let mask = xor_all & (-xor_all);

When to Use This Pattern

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

Common Mistakes

Mistake: Not finding the rightmost set bit correctly, causing wrong grouping
Fix: Use mask = xor_all & (-xor_all) to isolate the rightmost set bit

Mistake: XORing all elements again instead of separating into two groups
Fix: Divide elements into two groups based on mask bit and XOR separately

Summary

Finds two unique numbers in an array where all others appear twice using XOR and bit manipulation.

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

The key insight is to use XOR to find differing bits and split the array to isolate unique elements.

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