Two Non Repeating Elements in Array Using XOR in DSA Java

Mental Model

Use XOR to cancel out pairs and isolate two unique numbers by splitting the array into two groups based on a set bit.

Analogy: Imagine you have pairs of socks mixed with two unique socks. By shaking the pile and separating socks by a unique thread color, you can find the two unmatched socks easily.

Array: [2, 3, 7, 9, 2, 3]
XOR all: 7 ⊕ 9 = ?
Split by set bit:
Group 1: numbers with bit set -> 7
Group 2: numbers without bit set -> 9

Dry Run Walkthrough

Input: array: [2, 3, 7, 9, 2, 3]

Goal: Find the two numbers that appear only once (7 and 9) while all others appear twice

Step 1: XOR all elements to get xor_all

2 ⊕ 3 ⊕ 7 ⊕ 9 ⊕ 2 ⊕ 3 = 14 (binary 1110)

Why: XOR cancels pairs, leaving XOR of two unique numbers

Step 2: Find rightmost set bit in xor_all (14) -> 2 (binary 0010)

Set bit mask = 2

Why: This bit differs between the two unique numbers

Step 3: Divide array into two groups based on set bit and XOR separately

Group 1 (bit set): 3, 7, 3
Group 2 (bit not set): 2, 9, 2

Why: Separating numbers ensures unique numbers fall into different groups

Step 4: XOR Group 1: 3 ⊕ 7 ⊕ 3 = 7

Group 1 XOR = 7

Why: Pairs cancel out, leaving the unique number 7

Step 5: XOR Group 2: 2 ⊕ 9 ⊕ 2 = 9

Group 2 XOR = 9

Why: The unique number in this group

Step 6: The XOR results of the groups are the unique numbers

x = 7, y = 9

Why: Each group contains pairs that cancel out and exactly one unique number

Result:

Unique numbers: 7 and 9

Annotated Code

DSA Java

public class TwoNonRepeating {
    // Function to find two unique numbers
    public static int[] findTwoUnique(int[] arr) {
        int xor_all = 0;
        // XOR all elements to get xor of two unique numbers
        for (int num : arr) {
            xor_all ^= num; // accumulate XOR
        }
        // Find rightmost set bit in xor_all
        int set_bit = xor_all & (-xor_all);
        int x = 0, y = 0;
        // Divide elements into two groups and XOR separately
        for (int num : arr) {
            if ((num & set_bit) != 0) {
                x ^= num; // XOR group with set bit
            } else {
                y ^= num; // XOR group without set bit
            }
        }
        return new int[]{x, y};
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 7, 9, 2, 3};
        int[] result = findTwoUnique(arr);
        System.out.println(result[0] + " " + result[1]);
    }
}

xor_all ^= num; // accumulate XOR

XOR all elements to isolate XOR of two unique numbers

int set_bit = xor_all & (-xor_all);

Find rightmost set bit to differentiate two unique numbers

if ((num & set_bit) != 0) { x ^= num; } else { y ^= num; }

Divide elements into two groups and XOR separately to isolate unique numbers

Output

7 9

Complexity Analysis

Time: O(n) because we traverse the array a few times linearly

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Better than using hash maps which use O(n) space; XOR approach uses constant space

Edge Cases

Array with only two elements both unique

Returns those two elements directly

DSA Java

xor_all ^= num; // accumulate XOR

Array with all elements repeated except two unique

Correctly finds the two unique elements

DSA Java

if ((num & set_bit) != 0) { x ^= num; } else { y ^= num; }

Array with negative numbers

Works correctly because XOR works on bits regardless of sign

DSA Java

int set_bit = xor_all & (-xor_all);

When to Use This Pattern

When you see a problem asking for two unique numbers among duplicates, reach for the XOR splitting pattern because it isolates unique elements efficiently.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly
Fix: Use xor_all & (-xor_all) to get the rightmost set bit reliably

Mistake: Not dividing elements into two groups based on set bit
Fix: Separate elements by checking the set bit to isolate unique numbers

Summary

Finds two unique numbers in an array where all others appear twice using XOR.

Use when you need to find exactly two non-repeating elements among duplicates.

The key insight is to XOR all elements, find a differing bit, and split the array to isolate each unique number.

Practice

1. What is the main idea behind using XOR to find two non-repeating elements in an array where all other elements repeat twice?

easy

A. XOR removes duplicates by summing elements

B. XOR counts the frequency of each element

C. XOR sorts the array to separate unique elements

D. XOR of all elements gives XOR of the two unique elements

Solution

1. Step 1: XOR all elements in the array

   When we XOR all elements, pairs cancel out because x ^ x = 0, leaving XOR of the two unique elements.

2. Step 2: Use the XOR result to separate unique elements

   The XOR result has set bits where the two unique elements differ, helping to divide elements into two groups.

3. Final Answer:

   XOR of all elements gives XOR of the two unique elements -> Option D

4. Quick Check:

   XOR all = unique1 ^ unique2 [OK]

Hint: XOR all elements to isolate combined unique XOR [OK]

Common Mistakes:

• Thinking XOR counts frequency
• Assuming XOR sorts elements
• Using sum instead of XOR

2. Which of the following Java code snippets correctly initializes the XOR variable to find two unique elements in an integer array arr?

easy

A. int xor = 1; for(int num : arr) xor += num;

B. int xor = 0; for(int num : arr) xor ^= num;

C. int xor = arr[0]; for(int i = 0; i < arr.length; i++) xor ^= arr[i];

D. int xor = 0; for(int i = 0; i < arr.length; i++) xor = xor + arr[i];

Solution

1. Step 1: Initialize XOR to zero and XOR all elements

   Starting with zero ensures XOR accumulates correctly. Using a for-each loop with ^= operator applies XOR to each element.

2. Step 2: Check correctness of other options

   int xor = 1; for(int num : arr) xor += num; uses addition, not XOR. int xor = arr[0]; for(int i = 0; i < arr.length; i++) xor ^= arr[i]; incorrectly loops from i=0 after initializing with arr[0], XORing arr[0] twice which cancels it out. int xor = 0; for(int i = 0; i < arr.length; i++) xor = xor + arr[i]; uses addition, not XOR.

3. Final Answer:

   int xor = 0; for(int num : arr) xor ^= num; -> Option B

4. Quick Check:

   Initialize xor=0 and XOR all elements [OK]

Hint: Start XOR with 0 and XOR all elements [OK]

Common Mistakes:

• Using addition instead of XOR
• Starting XOR with non-zero value
• Using wrong loop syntax

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

int[] arr = {2, 3, 7, 9, 2, 3};
int xor = 0;
for (int num : arr) xor ^= num;
int setBit = xor & (-xor);
int x = 0, y = 0;
for (int num : arr) {
  if ((num & setBit) != 0) x ^= num;
  else y ^= num;
}
System.out.println(x + ", " + y);

medium

A. 7, 9

B. 2, 3

C. 0, 0

D. 9, 7

Solution

1. Step 1: XOR all elements to get xor = 7 ^ 9 = 14

   Pairs (2,2) and (3,3) cancel out, leaving xor = 7 ^ 9 = 14.

2. Step 2: Find rightmost set bit and separate elements

   setBit = 14 & (-14) = 2. Elements with bit 2 set: 2, 2, 3, 3, 7, 9 split into groups. XOR group 1: 7, XOR group 2: 9.

3. Final Answer:

   7, 9 -> Option A

4. Quick Check:

   Unique elements are 7 and 9 [OK]

Hint: Use rightmost set bit to split and XOR groups [OK]

Common Mistakes:

• Mixing order of output
• Not using rightmost set bit correctly
• Confusing pairs with unique elements

4. Identify the error in the following Java code snippet that attempts to find two non-repeating elements using XOR:

int[] arr = {4, 1, 2, 1, 2, 5};
int xor = 0;
for (int i = 0; i <= arr.length; i++) {
  xor ^= arr[i];
}
int setBit = xor & (-xor);
int x = 0, y = 0;
for (int num : arr) {
  if ((num & setBit) != 0) x ^= num;
  else y ^= num;
}
System.out.println(x + ", " + y);

medium

A. Loop condition should be i < arr.length, not i <= arr.length

B. XOR initialization should be arr[0], not 0

C. setBit calculation is incorrect

D. Second loop should use index instead of for-each

Solution

1. Step 1: Check loop boundary in XOR calculation

   The for loop uses i <= arr.length, which causes ArrayIndexOutOfBoundsException because valid indices are 0 to arr.length-1.

2. Step 2: Correct loop condition to i < arr.length

   Changing to i < arr.length fixes the error and allows proper XOR of all elements.

3. Final Answer:

   Loop condition should be i < arr.length, not i <= arr.length -> Option A

4. Quick Check:

   Array index must be within bounds [OK]

Hint: Use i < length, not i <= length in loops [OK]

Common Mistakes:

• Using wrong loop boundary causing runtime error
• Incorrect XOR initialization
• Misunderstanding setBit calculation

5. Given an array arr = {10, 20, 10, 30, 40, 20, 50, 40}, which Java code snippet correctly finds the two non-repeating elements using XOR and prints them in ascending order?

hard

A. int xor = 0;
for(int num : arr) xor ^= num;
int setBit = xor & (-xor);
int x = 0, y = 0;
for(int num : arr) {
if((num & setBit) != 0) x ^= num;
else y ^= num;
}
System.out.println(x + y);

B. int xor = arr[0];
for(int i=1; i

C. int xor = 0;
for(int num : arr) xor ^= num;
int setBit = xor & (-xor);
int x = 0, y = 0;
for(int num : arr) {
if((num & setBit) != 0) x ^= num;
else y ^= num;
}
System.out.println(Math.min(x,y) + ", " + Math.max(x,y));

D. int xor = 0;
for(int num : arr) xor ^= num;
int setBit = xor & (-xor);
int x = 0, y = 0;
for(int num : arr) {
if((num & setBit) == 0) x ^= num;
else y ^= num;
}
System.out.println(x + ", " + y);

Solution

1. Step 1: XOR all elements and find rightmost set bit

   XOR of all elements gives xor = 30 ^ 50 = 44. setBit = 44 & (-44) = 4.

2. Step 2: Separate elements into two groups and XOR each group

   Elements with bit 4 set XOR to 50, others XOR to 30.

3. Step 3: Print the two unique elements in ascending order

   Using Math.min and Math.max prints "30, 50" as required.

4. Final Answer:

   Prints 30, 50 in ascending order -> Option C

5. Quick Check:

   Use XOR groups and sort output [OK]

Hint: Use XOR groups and Math.min/Math.max to order output [OK]

Common Mistakes:

• Using bitwise OR instead of AND for setBit
• Swapping group conditions incorrectly
• Printing sum instead of elements