Two Non Repeating Elements in Array Using XOR in DSA Rust - Execution Trace

Concept Flow - Two Non Repeating Elements in Array Using XOR

Start with array

↓

Compute XOR of all elements

↓

Find rightmost set bit in XOR result

↓

Divide elements into two groups based on set bit

↓

Compute XOR of each group separately

↓

Result: two unique non-repeating elements

We first XOR all elements to get XOR of two unique numbers. Then find a set bit to split array into two groups and XOR each group to find the unique elements.

Execution Sample

DSA Rust

let arr = [2, 3, 7, 9, 2, 3];
let mut xor_all = 0;
for &num in &arr {
    xor_all ^= num;
}
// xor_all = 7 ^ 9 = 14
let set_bit = xor_all & (!(xor_all - 1));
// set_bit = 2
let (mut x, mut y) = (0, 0);
for &num in &arr {
    if num & set_bit != 0 { x ^= num; } else { y ^= num; }
}
// x = 7, y = 9

This code finds two unique numbers in the array by XORing all, then splitting by a set bit and XORing groups.

Execution Table

Step	Operation	XOR All	Set Bit	Group 1 XOR (x)	Group 2 XOR (y)	Visual State
1	XOR with 2	0 ^ 2 = 2				[2]
2	XOR with 3	2 ^ 3 = 1				[2,3]
3	XOR with 7	1 ^ 7 = 6				[2,3,7]
4	XOR with 9	6 ^ 9 = 15				[2,3,7,9]
5	XOR with 2	15 ^ 2 = 13				[2,3,7,9,2]
6	XOR with 3	13 ^ 3 = 14				[2,3,7,9,2,3]
7	Find rightmost set bit	14	2 (binary 10)
8	Divide and XOR group 1 (bit set)			7		[7]
9	Divide and XOR group 2 (bit not set)				9	[9]
10	Result			7	9	Unique elements: 7 and 9

💡 All elements processed, two unique elements found by group XOR.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
xor_all	0	2	1	6	15	13	14	14	14	14	14
set_bit	N/A	N/A	N/A	N/A	N/A	N/A	N/A	2	2	2	2
x (group 1 XOR)	0	0	0	0	0	0	0	0	7	7	7
y (group 2 XOR)	0	0	0	0	0	0	0	0	0	9	9

Key Moments - 3 Insights

Why do we XOR all elements first?

XORing all elements cancels out duplicates because XOR of a number with itself is zero, leaving XOR of the two unique numbers (see execution_table steps 1-6).

How do we find the rightmost set bit in XOR result?

We use xor_all & (!(xor_all - 1)) to isolate the rightmost set bit, which helps split numbers into two groups (see execution_table step 7).

Why split elements into two groups based on set bit?

Because the two unique numbers differ at that bit, splitting ensures each unique number falls into different groups, allowing separate XOR to find them (see steps 8-9).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of xor_all?

A 15

B 14

C 13

D 6

💡 Hint

Check the 'XOR All' column at step 6 in execution_table.

At which step does the algorithm find the rightmost set bit?

A Step 7

B Step 9

C Step 5

D Step 3

💡 Hint

Look for the 'Find rightmost set bit' operation in execution_table.

If the set bit was different, how would group XORs change?

A Groups would be the same

B xor_all would change

C Groups would change, resulting in different x and y values

D No effect on unique elements

💡 Hint

Refer to variable_tracker for x and y values after grouping.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor_all.
2. Find rightmost set bit in xor_all.
3. Split array into two groups by this bit.
4. XOR each group to find unique elements.
5. Time: O(n), Space: O(1).

Full Transcript

This concept finds two unique non-repeating elements in an array where all others repeat twice. First, XOR all elements to get xor_all, which is XOR of the two unique numbers. Then find the rightmost set bit in xor_all to split elements into two groups. Each group contains one unique number and duplicates. XORing each group separately cancels duplicates, leaving the unique numbers. This method uses bitwise XOR properties and runs efficiently in linear time with constant space.

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