Two Non Repeating Elements in Array Using XOR in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based two unique elements finder

What is the output of this Rust code that finds two unique numbers in an array where every other number repeats twice?

DSA Rust

fn find_two_unique(nums: &[i32]) -> (i32, i32) {
    let xor_all = nums.iter().fold(0, |acc, &x| acc ^ x);
    let rightmost_set_bit = xor_all & (-xor_all);
    let (mut x, mut y) = (0, 0);
    for &num in nums {
        if num & rightmost_set_bit != 0 {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    (x, y)
}

fn main() {
    let arr = [2, 4, 7, 9, 2, 4];
    let result = find_two_unique(&arr);
    println!("({}, {})", result.0, result.1);
}

A (2, 4)

B (9, 7)

C (7, 9)

D (0, 0)

💡 Hint

Focus on how XOR cancels out duplicate numbers and how the rightmost set bit helps separate the two unique numbers.

The XOR of all numbers gives xor_all = 7 ^ 9. The rightmost set bit in xor_all helps split numbers into two groups. XORing each group separately gives the two unique numbers 7 and 9. The order is (7, 9) because x accumulates numbers with the set bit.

🧠 Conceptual

intermediate

Why XOR helps find two unique elements?

Why does XOR operation help in finding two unique elements in an array where every other element repeats twice?

A Because XOR multiplies numbers to find unique products

B Because XOR adds numbers together to find the sum of unique elements

C Because XOR sorts the array to separate unique elements

D Because XOR of two identical numbers is zero, so duplicates cancel out leaving XOR of unique elements

💡 Hint

Think about what happens when you XOR a number with itself.

XOR of a number with itself is zero, so all duplicates cancel out. The remaining XOR is the XOR of the two unique numbers.

🔧 Debug

advanced

Identify the error in this Rust code for two unique elements

What error does this Rust code produce when trying to find two unique elements using XOR?

DSA Rust

fn find_two_unique(nums: &[i32]) -> (i32, i32) {
    let xor_all = nums.iter().fold(0, |acc, &x| acc ^ x);
    let rightmost_set_bit = xor_all & (xor_all - 1);
    let (mut x, mut y) = (0, 0);
    for &num in nums {
        if num & rightmost_set_bit != 0 {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    (x, y)
}

fn main() {
    let arr = [1, 2, 1, 3, 2, 5];
    let result = find_two_unique(&arr);
    println!("({}, {})", result.0, result.1);
}

A The output is incorrect because rightmost_set_bit is wrongly calculated

B Syntax error due to missing semicolon

C Runtime panic due to integer overflow

D Compilation error due to type mismatch

💡 Hint

Check how rightmost_set_bit is calculated and what it should represent.

The code uses xor_all & (xor_all - 1) which clears the rightmost set bit instead of isolating it. This causes wrong grouping and incorrect output.

❓ Predict Output

advanced

Output of XOR grouping with negative numbers

What is the output of this Rust code that finds two unique numbers including a negative number?

DSA Rust

fn find_two_unique(nums: &[i32]) -> (i32, i32) {
    let xor_all = nums.iter().fold(0, |acc, &x| acc ^ x);
    let rightmost_set_bit = xor_all & (-xor_all);
    let (mut x, mut y) = (0, 0);
    for &num in nums {
        if num & rightmost_set_bit != 0 {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    (x, y)
}

fn main() {
    let arr = [-1, 2, 3, 2, 3, 4];
    let result = find_two_unique(&arr);
    println!("({}, {})", result.0, result.1);
}

A (4, -1)

B (-1, 4)

C (2, 3)

D (0, 0)

💡 Hint

Remember XOR works with negative numbers too. The order depends on grouping by the rightmost set bit.

The XOR groups separate -1 and 4 correctly. The output is (-1, 4) because -1 falls in the group with the set bit.

🚀 Application

expert

Number of items in the resulting vector after grouping by rightmost set bit

Given the array [6, 1, 4, 1, 6, 9], after computing xor_all and grouping elements by the rightmost set bit of xor_all, how many elements are in the group where the bit is set?

DSA Rust

let arr = [6, 1, 4, 1, 6, 9];
let xor_all = arr.iter().fold(0, |acc, &x| acc ^ x);
let rightmost_set_bit = xor_all & (-xor_all);
let group_set_bit: Vec<i32> = arr.iter().cloned().filter(|&x| x & rightmost_set_bit != 0).collect();
println!("{}", group_set_bit.len());

A 3

B 2

C 4

D 1

💡 Hint

Calculate xor_all first, find its rightmost set bit, then count elements with that bit set.

xor_all = 6 ^ 1 ^ 4 ^ 1 ^ 6 ^ 9 = 13 (binary 1101). The rightmost set bit is 1 (binary 0001). Elements with bit 1 set: 6 (110) no, 1 (001) yes, 4 (100) no, 1 (001) yes, 6 (110) no, 9 (1001) yes. So elements with bit 1 set are 1, 1, 9 → 3 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