Two Non Repeating Elements in Array Using XOR in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using XOR to find two non-repeating elements in an array?

XOR of all elements gives XOR of the two unique elements because pairs cancel out. Then, use a set bit to separate elements into two groups to find each unique element.

beginner

Why does XOR of two identical numbers result in zero?

Because XOR compares bits and returns 1 only if bits differ. Same bits XORed give 0, so a number XORed with itself is 0.

intermediate

How do you find a set bit in the XOR of two unique numbers?

Use 'xor & (-xor)' to isolate the rightmost set bit, which helps to divide numbers into two groups based on that bit.

beginner

What is the time complexity of finding two non-repeating elements using XOR?

The time complexity is O(n) because the array is traversed a constant number of times.

intermediate

Explain why dividing elements into two groups based on a set bit helps find the two unique elements.

The two unique elements differ at that bit, so they fall into different groups. XORing each group cancels duplicates, leaving one unique element per group.

What does XOR of a number with zero return?

A One

B Zero

C The number itself

D Negative of the number

XOR with zero leaves the number unchanged.

If XOR of all elements in an array is 0, what does it imply?

A All elements appear twice

B There are two unique elements

C Array is empty

D Array has only one element

Pairs cancel out in XOR, so XOR 0 means all elements appear twice.

How do you isolate the rightmost set bit of a number 'x'?

A x & (-x)

B x | (-x)

C ~x

D x ^ (-x)

x & (-x) isolates the rightmost set bit.

Why do we divide elements into two groups based on a set bit in XOR?

A To separate duplicates

B To separate the two unique elements

C To sort the array

D To find the maximum element

The two unique elements differ at that bit, so dividing helps isolate them.

What is the space complexity of the XOR method for finding two unique elements?

A O(n)

B O(n^2)

C O(log n)

D O(1)

Only a few variables are used, so space complexity is constant.

Describe the step-by-step process to find two non-repeating elements in an array using XOR.

Think about how XOR cancels pairs and how a set bit helps separate unique numbers.

Explain why XOR operation is useful for finding unique elements in an array where others appear twice.

Focus on how XOR behaves with pairs and unique numbers.

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