Find the Only Non Repeating Element Using XOR in DSA Java - 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

↓

Final result holds the non-repeating element

↓

Return result

We start with zero and XOR it with every element in the array. Pairs cancel out, leaving only the unique element.

Execution Sample

DSA Java

int findUnique(int[] arr) {
  int result = 0;
  for (int num : arr) {
    result ^= num;
  }
  return result;
}

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

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State (XOR Result)
1	Initialize result	N/A	N/A	0	0
2	XOR with element	2	0	2	2
3	XOR with element	3	2	1	1
4	XOR with element	2	1	3	3
5	XOR with element	4	3	7	7
6	XOR with element	3	7	4	4
7	XOR with element	4	4	0	0
8	XOR with element	5	0	5	5
9	End of array	N/A	5	5	5

💡 All repeating elements cancel out, leaving 5 as the only non-repeating element.

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

Key Moments - 3 Insights

Why does XORing a number with itself result in zero?

Because XOR of two identical bits is 0, so when a number is XORed with itself, all bits cancel out to zero. This is shown in steps 4 and 6 where XOR with repeated elements resets the result.

Why do we start with result = 0?

Zero is the identity for XOR, meaning XORing zero with any number returns that number unchanged. This allows the first element to set the initial result, as seen in step 2.

What happens if the array has only one element?

The loop XORs zero with that single element, so the result is that element itself, correctly identifying it as unique.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'result' after XORing with the third element?

A 1

B 3

C 2

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 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look for 'Result After XOR' column where value is 0 after initial steps

If the array was [1, 1, 2], what would be the final 'result'?

A 1

B 2

C 0

D 3

💡 Hint

XOR cancels pairs; check variable_tracker logic for unique element

Concept Snapshot

Find unique element using XOR:
- Initialize result = 0
- XOR result with each array element
- Pairs cancel out to 0
- Result ends as unique element
- Works only if one element is unique

Full Transcript

This concept uses XOR to find the only non-repeating element in an array. Starting with zero, we XOR it with every element. Because XOR of a number with itself is zero, all repeating elements cancel out. The final XOR result is the unique element. The code loops through the array, updating the result each time. 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 -1

Solution

1. Step 1: Understand XOR property for identical numbers

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

2. Step 2: Apply XOR on example

   For example, 5 XOR 5 = 0.

3. Final Answer:

   It returns 0 -> Option A

4. Quick Check:

   X XOR X = 0 [OK]

Hint: X XOR X always equals zero [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to initialize an integer variable named result to 0 in Java?

easy

A. int result := 0;

B. int result == 0;

C. int result = 0;

D. int result = zero;

Solution

1. Step 1: Recall Java variable initialization syntax

   In Java, variables are declared with type, name, and assignment using single equals sign.

2. Step 2: Check each option

   int result = 0; uses correct syntax: int result = 0;. Others have syntax errors.

3. Final Answer:

   int result = 0; -> Option C

4. Quick Check:

   Correct Java variable initialization [OK]

Hint: Use single '=' for assignment in Java [OK]

Common Mistakes:

• Using '==' instead of '='
• Using ':=' which is not Java syntax
• Assigning undefined variable 'zero'

3. What will be the output of the following Java code?

int[] arr = {2, 3, 2, 4, 3};
int result = 0;
for (int num : arr) {
    result ^= num;
}
System.out.println(result);

medium

A. 4

B. 3

C. 2

D. 0

Solution

1. Step 1: Apply XOR operation on array elements

   Start with result=0, XOR with each element: 0^2=2, 2^3=1, 1^2=3, 3^4=7, 7^3=4.

2. Step 2: Final XOR result is the non-repeating element

   The only element that does not repeat is 4, which is the final XOR result.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Only non-repeating element = 4 [OK]

Hint: XOR all elements; result is unique number [OK]

Common Mistakes:

• Not starting XOR with 0
• Miscomputing XOR steps
• Assuming sum instead of XOR

4. Identify the error in the following Java code snippet that tries to find the only non-repeating element using XOR:

int[] arr = {1, 2, 1, 3, 2};
int result;
for (int num : arr) {
    result ^= num;
}
System.out.println(result);

medium

A. System.out.println syntax is wrong

B. Array 'arr' is not declared properly

C. For-each loop syntax is incorrect

D. Variable 'result' is not initialized before XOR operation

Solution

1. Step 1: Check variable initialization

   The variable 'result' is declared but not initialized before XOR operation, causing a compile error.

2. Step 2: Correct initialization needed

   Initialize 'result' to 0 before the loop to avoid error.

3. Final Answer:

   Variable 'result' is not initialized before XOR operation -> Option D

4. Quick Check:

   Uninitialized variable causes error [OK]

Hint: Always initialize XOR accumulator to 0 [OK]

Common Mistakes:

• Forgetting to initialize result
• Misusing loop syntax
• Incorrect print statement

5. Given an array where every element repeats twice except one element which repeats thrice, can the XOR method find the unique element? What will be the output of this code?

int[] arr = {5, 5, 5, 7, 7, 8, 8};
int result = 0;
for (int num : arr) {
    result ^= num;
}
System.out.println(result);

hard

A. 5

B. Cannot find unique element correctly

C. 0

D. 7

Solution

1. Step 1: Understand XOR property for odd/even counts

   XOR cancels even number of identical elements to 0; odd count leaves the element.

2. Step 2: Analyze given array and XOR result

   5 appears 3 times (odd) -> XOR of three identical numbers is not the number itself; XOR of 5^5=0, 0^5=5, but this pattern does not hold for triple repeats in general.

3. Step 3: Conclusion

   XOR method cannot reliably find the unique element when counts are not exactly twice except one.

4. Final Answer:

   Cannot find unique element correctly -> Option B

5. Quick Check:

   XOR fails for elements repeating thrice [OK]

Hint: XOR only works when all elements except one appear exactly twice [OK]

Common Mistakes:

• Thinking XOR finds unique element with triple repeats
• Miscomputing XOR of three identical numbers as the number itself
• Ignoring that XOR only cancels pairs