Find the Only Non Repeating Element Using XOR in DSA Rust - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

For each element in array

↓

Apply XOR: result = result XOR element

↓

Repeat for all elements

↓

Result holds the unique element

↓

Return result

We start with zero and XOR it with every element in the array. Because XOR of two same numbers is zero, all repeating elements cancel out, leaving only the unique element.

Execution Sample

DSA Rust

fn find_unique(arr: &[i32]) -> i32 {
    let mut result = 0;
    for &num in arr {
        result ^= num;
    }
    result
}

This code finds the only non-repeating element in an array by XORing all elements.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Explanation
1	Initialize result	N/A	0	0	Start with result = 0
2	XOR with element	2	0	2	0 XOR 2 = 2
3	XOR with element	3	2	1	2 XOR 3 = 1
4	XOR with element	2	1	3	1 XOR 2 = 3
5	XOR with element	4	3	7	3 XOR 4 = 7
6	XOR with element	3	7	4	7 XOR 3 = 4
7	XOR with element	4	4	0	4 XOR 4 = 0
8	XOR with element	5	0	5	0 XOR 5 = 5
9	End	N/A	5	5	Result is 5, the unique element

💡 All repeating elements cancel out, leaving the unique element 5 in result.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	0	2	1	3	7	4	0	5	5
current element	N/A	2	3	2	4	3	4	5	N/A

Key Moments - 3 Insights

Why does XORing a number with itself result in zero?

Because XOR compares bits and returns 0 when bits are the same. So, any number XOR itself cancels out to zero, as shown in steps 7 and 6 where repeated elements reduce result.

Why do we start result with zero?

Zero is the identity for XOR, meaning XOR with zero leaves the number unchanged. Starting with zero ensures the first element sets the initial result, as in step 2.

What if the array has no unique element?

If all elements repeat, XORing all will result in zero. The code returns zero, which means no unique element found, as the exit note explains.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'result' after XORing the third element?

A 3

B 2

C 1

D 0

💡 Hint

Check row 3 in the execution_table under 'Result After XOR'

At which step does the 'result' become zero again after starting?

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look at the 'Result After XOR' column in execution_table for zero values after initialization

If the array had no unique element, what would the final 'result' be?

A The last element in the array

B Zero

C The first element in the array

D Undefined

💡 Hint

Refer to the exit_note and key_moments about all elements cancelling out

Concept Snapshot

Find unique element by XORing all array elements.
XOR of same numbers is zero, so duplicates cancel out.
Start with result = 0.
XOR result with each element.
Final result is the unique element.
Works only if exactly one element is unique.

Full Transcript

This concept finds the only non-repeating element in an array by using XOR operation. We start with a variable result set to zero. Then, for each element in the array, we XOR it with result. Because XOR of a number with itself is zero, all repeating elements cancel out. The final value of result after processing all elements is the unique element. If no unique element exists, the result will be zero. This method is efficient and uses constant extra space.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns 0

B. It returns the number itself

C. It returns 1

D. It returns the sum of the numbers

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself is always 0 because bits cancel out.

2. Step 2: Apply this property to the question

   Since the two numbers are identical, XOR returns 0.

3. Final Answer:

   It returns 0 -> Option A

4. Quick Check:

   X XOR X = 0 [OK]

Hint: XOR of same numbers always zero [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with addition
• Assuming XOR returns 1 for identical numbers

2. Which Rust syntax correctly initializes a variable to zero for XOR operation?

easy

A. let mut result = 0;

B. let result = 0;

C. let mut result = 1;

D. let mut result = None;

Solution

1. Step 1: Identify mutable variable declaration

   We need a mutable variable to update XOR results, so use 'mut'.

2. Step 2: Initialize variable to zero

   Zero is the identity for XOR, so initialize with 0.

3. Final Answer:

   let mut result = 0; -> Option A

4. Quick Check:

   Mutable zero initialization for XOR [OK]

Hint: Use 'let mut var = 0;' for XOR accumulator [OK]

Common Mistakes:

• Not using 'mut' for variable to update
• Initializing with 1 instead of 0
• Using Option type instead of integer

3. What is the output of this Rust code?

fn main() {
    let arr = [2, 3, 5, 4, 5, 3, 4];
    let mut result = 0;
    for &num in &arr {
        result ^= num;
    }
    println!("{}", result);
}

medium

A. 4

B. 5

C. 0

D. 2

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^5=4, 4^4=0, 0^5=5, 5^3=6, 6^4=2.

2. Step 2: Identify the non-repeating element

   The final XOR result is 2, which is the only number not repeated.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Final XOR = 2 [OK]

Hint: XOR all numbers; result is unique element [OK]

Common Mistakes:

• Miscomputing XOR steps
• Assuming repeated numbers affect result
• Confusing output with repeated elements

4. Identify the error in this Rust code that tries to find the non-repeating element using XOR:

fn main() {
    let arr = [1, 2, 1, 3, 2];
    let mut result = 0;
    for num in arr {
        result = result ^ num;
    }
    println!("{}", result);
}

medium

A. Missing '&' in for loop to borrow elements

B. No error, code works correctly

C. Incorrect initialization of result variable

D. Using '=' instead of '^=' operator

Solution

1. Step 1: Check for borrowing in for loop

   Iterating over array by value is allowed; no '&' needed.

2. Step 2: Verify XOR operation and initialization

   Result initialized to 0 and XOR applied correctly with '=' operator.

3. Final Answer:

   No error, code works correctly -> Option B

4. Quick Check:

   Code runs and finds unique element [OK]

Hint: XOR with '=' works; no borrow needed for array iteration [OK]

Common Mistakes:

• Thinking '&' is mandatory in for loop
• Confusing '=' with '^=' operator
• Assuming initialization must be different

5. Given an array where every element repeats twice except one element which repeats thrice, can XOR find the unique element? Why or why not?

hard

A. Yes, XOR works for any number of duplicates

B. No, XOR works only if unique element appears once

C. No, XOR only works if all duplicates appear exactly twice

D. Yes, but only if array length is odd

Solution

1. Step 1: Understand XOR behavior with duplicates

   XOR cancels pairs of identical numbers (duplicates appearing twice).

2. Step 2: Analyze effect of triplicate duplicates

   Triplicates do not cancel out with XOR, so result is incorrect.

3. Final Answer:

   No, XOR only works if all duplicates appear exactly twice -> Option C

4. Quick Check:

   XOR cancels pairs, not triplets [OK]

Hint: XOR cancels pairs only, not triplets [OK]

Common Mistakes:

• Assuming XOR works for any duplicate count
• Confusing unique element count with duplicates
• Ignoring XOR cancellation properties