Find the Only Non Repeating Element Using XOR in DSA Java

Mental Model

XOR of a number with itself is zero, and XOR with zero is the number itself. So XORing all numbers cancels out duplicates, leaving the unique one.

Analogy: Imagine you have pairs of socks in a drawer. If you take out all socks and pair them up, the one sock left without a pair is the unique one.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 -> 2
2 ⊕ 3 -> 1
1 ⊕ 2 -> 3
3 ⊕ 4 -> 7
7 ⊕ 3 -> 4
Result: 4 (unique element)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result with first XOR to start cancelling duplicates

Step 2: XOR result with next element 3

result = 2 ⊕ 3 = 1

Why: XOR with 3 updates result to reflect unique so far

Step 3: XOR result with next element 2

result = 1 ⊕ 2 = 3

Why: XOR with 2 cancels previous 2, leaving 3

Step 4: XOR result with next element 4

result = 3 ⊕ 4 = 7

Why: XOR with 4 adds new unique element

Step 5: XOR result with last element 3

result = 7 ⊕ 3 = 4

Why: XOR with 3 cancels previous 3, leaving 4 as unique

Result:

Final result = 4
Unique element is 4

Annotated Code

DSA Java

public class UniqueElementXOR {
    // Function to find the only non-repeating element using XOR
    public static int findUnique(int[] arr) {
        int result = 0; // start with 0 because XOR with 0 is number itself
        for (int num : arr) {
            result ^= num; // XOR accumulates unique element by cancelling duplicates
        }
        return result; // result holds the unique element
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 2, 4, 3};
        int unique = findUnique(arr);
        System.out.println("Unique element is " + unique);
    }
}

int result = 0; // start with 0 because XOR with 0 is number itself

initialize result to zero to start XOR accumulation

for (int num : arr) {

iterate over each element to process all numbers

result ^= num; // XOR accumulates unique element by cancelling duplicates

XOR current number with result to cancel duplicates

return result; // result holds the unique element

return the final XOR result which is the unique number

Output

Unique element is 4

Complexity Analysis

Time: O(n) because we traverse the array once to XOR all elements

Space: O(1) because we use only one variable to store XOR result

vs Alternative: Compared to using a hash map to count frequencies (O(n) time and O(n) space), XOR uses constant space and is more efficient

Edge Cases

Array with only one element

Returns that element as unique

DSA Java

for (int num : arr) {

Array where all elements except one appear twice

Correctly returns the single unique element

DSA Java

result ^= num;

Empty array

Returns 0 as no elements to XOR

DSA Java

int result = 0;

When to Use This Pattern

When you see a problem asking for a single unique element among duplicates, reach for the XOR pattern because it cancels pairs efficiently in one pass.

Common Mistakes

Mistake: Starting XOR result with first array element instead of zero
Fix: Initialize result to zero to handle empty arrays and simplify logic

Mistake: Using addition or subtraction instead of XOR
Fix: Use XOR operator (^) because it cancels duplicates correctly

Summary

Finds the single non-repeating element in an array where all others repeat twice.

Use when you need to find a unique element efficiently without extra space.

XORing all elements cancels duplicates and leaves the unique element as the result.

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