Two Non Repeating Elements in Array Using XOR in DSA Java - Execution Trace

Concept Flow - Two Non Repeating Elements in Array Using XOR

Start with array

↓

Compute XOR of all elements

↓

Find rightmost set bit in XOR result

↓

Divide elements into two groups based on set bit

↓

Compute XOR separately in each group

↓

Result: two unique non-repeating elements

We first XOR all elements to get XOR of two unique numbers. Then find a set bit to separate elements into two groups and XOR each group to find the unique elements.

Execution Sample

DSA Java

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;
}

This code finds two unique non-repeating elements in an array where all other elements repeat twice.

Execution Table

Step	Operation	XOR Value	Set Bit	Group XOR x	Group XOR y	Visual State
1	XOR all elements: xor=0^2	2	-	-	-	[2]
2	XOR all elements: xor=2^3	1	-	-	-	[2,3]
3	XOR all elements: xor=1^7	6	-	-	-	[2,3,7]
4	XOR all elements: xor=6^9	15	-	-	-	[2,3,7,9]
5	XOR all elements: xor=15^2	13	-	-	-	[2,3,7,9,2]
6	XOR all elements: xor=13^3	14	-	-	-	[2,3,7,9,2,3]
7	Find rightmost set bit: setBit = 14 & (-14)	14	2 (binary 10)	-	-	-
8	Divide and XOR group x (bit set): x=0^2	14	2	2	0	[2]
9	Divide and XOR group x (bit set): x=2^3	14	2	1	0	[2,3]
10	Group x: x=1^7	14	2	6	0	[2,3,7]
11	Group y: y=0^9	14	2	6	9	[9]
12	Group x: x=6^2	14	2	4	9	[2,3,7,2]
13	Divide and XOR group x (bit set): x=4^3	14	2	7	9	[2,3,7,2,3]
14	Result: unique elements are x=7, y=9	14	2	7	9	[7,9]

💡 All elements processed; two unique non-repeating elements found as 7 and 9.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 14
xor	0	14	14	14
setBit	-	-	2	2
x	0	0	0	7
y	0	0	0	9

Key Moments - 3 Insights

Why do we XOR all elements first?

XORing all elements cancels out duplicates because a^a=0, leaving XOR of only the two unique elements (see execution_table steps 1-6).

How do we find the rightmost set bit and why?

We use setBit = xor & (-xor) to isolate the rightmost set bit, which helps separate the two unique numbers into different groups (see step 7).

Why divide elements into two groups based on set bit?

Because the two unique numbers differ at that bit, grouping by that bit ensures each unique number falls into a different group, allowing separate XOR to find them (see steps 8-13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of setBit?

A 2

B 14

C 1

D 0

💡 Hint

Check the 'Set Bit' column at step 7 in execution_table.

At which step does the variable x first change from 0?

A Step 12

B Step 8

C Step 10

D Step 14

💡 Hint

Look at the 'Group XOR x' column in execution_table to see when x changes from 0.

If the array had no duplicates, how would the xor variable after step 6 change?

A It would be equal to the first element

B It would be 0

C It would be XOR of all elements

D It would be equal to the last element

💡 Hint

Refer to variable_tracker for xor value after step 6 and understand XOR behavior.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor of two unique numbers.
2. Find rightmost set bit in xor (setBit = xor & -xor).
3. Divide elements into two groups by setBit.
4. XOR each group separately to find unique elements.
5. Works because duplicates cancel out in XOR.

Full Transcript

This concept finds two unique non-repeating elements in an array where all other elements appear twice. First, XOR all elements to get xor of the two unique numbers. Then find the rightmost set bit in this xor to separate elements into two groups. XORing each group separately reveals the two unique elements. The execution table shows step-by-step XOR calculations and grouping. Variable tracker shows how xor, setBit, x, and y change. Key moments clarify why XOR is used, how the set bit is found, and why grouping works. Visual quiz tests understanding of these steps. This method efficiently finds two unique numbers in linear time without extra space.

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