Two Non Repeating Elements in Array Using XOR in DSA Java - Deep Dive

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

This topic teaches how to find two unique numbers in an array where every other number repeats exactly twice. Using a special operation called XOR, we can identify these two numbers without extra space or sorting. The method is efficient and works by cleverly separating the two unique numbers based on their differing bits.

Why it matters

Without this technique, finding two unique numbers among duplicates would require extra memory or slower sorting methods. This XOR approach saves time and space, making programs faster and more efficient. It is especially useful in large datasets or systems with limited memory, like embedded devices or real-time applications.

Where it fits

Before this, learners should understand basic bitwise operations, especially XOR, and how arrays work. After mastering this, they can explore more complex bit manipulation problems, hashing techniques, or advanced data structures like tries and bloom filters.

Mental Model

Core Idea

Using XOR, we can combine all numbers to cancel out duplicates and isolate the two unique numbers by splitting them based on a differing bit.

Think of it like...

Imagine you have pairs of identical gloves mixed in a box, except two gloves are unique and unmatched. By shaking the box and listening carefully, you can separate the gloves into two groups based on a small difference, like color or texture, and find the unique ones without looking at each glove individually.

Array: [a, a, b, b, x, y]
Step 1: XOR all elements -> result = x XOR y
Step 2: Find rightmost set bit in result -> mask
Step 3: Divide elements into two groups based on mask bit
Group 1: elements with bit set
Group 2: elements with bit not set
Step 4: XOR each group separately -> unique elements x and y

  ┌─────────────────────────────┐
  │ All elements XORed: x XOR y │
  └─────────────┬───────────────┘
                │
       Find rightmost set bit (mask)
                │
  ┌─────────────┴───────────────┐
  │                             │
Group 1 (bit set)          Group 2 (bit not set)
  │                             │
XOR all elements in       XOR all elements in
Group 1 -> x             Group 2 -> y

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does and its properties with numbers.

XOR (exclusive OR) compares two bits and returns 1 if they are different, 0 if the same. For example, 5 XOR 3 in binary is 0101 XOR 0011 = 0110 (which is 6). Important properties: - x XOR x = 0 (a number XOR itself is zero) - x XOR 0 = x (a number XOR zero is the number itself) - XOR is commutative and associative (order doesn't matter) These properties help cancel out duplicate numbers.

Result

Knowing XOR cancels duplicates and keeps unique bits.

Understanding XOR's canceling effect is the foundation for isolating unique numbers in arrays.

2

Foundation

Problem Setup: Array with Two Unique Numbers

Concept: Recognize the problem where all numbers repeat twice except two unique ones.

Given an array like [2, 3, 7, 9, 2, 3], numbers 7 and 9 appear once, others twice. The goal is to find these two unique numbers efficiently without extra space or sorting.

Result

Clear problem statement to find two unique numbers among duplicates.

Knowing the problem constraints guides the choice of XOR-based solution.

3

Intermediate

XOR All Elements to Combine Uniques

🤔Before reading on: Do you think XORing all elements will give one unique number or a combination of both? Commit to your answer.

Concept: XOR all array elements to get XOR of the two unique numbers combined.

When we XOR all elements, duplicates cancel out because x XOR x = 0. So the result is XOR of the two unique numbers, say x XOR y. This combined XOR holds bits where x and y differ.

Result

A single number representing x XOR y, which is non-zero since x != y.

Understanding that XOR of all elements isolates combined difference is key to separating the two unique numbers.

4

Intermediate

Find Rightmost Set Bit to Split Groups

🤔Before reading on: Do you think any set bit in x XOR y can help separate the two unique numbers? Commit to yes or no.

Concept: Use the rightmost set bit in x XOR y to divide numbers into two groups.

The rightmost set bit in x XOR y indicates a bit where x and y differ. We create a mask with this bit set. Then, split all numbers into two groups: - Group 1: numbers with this bit set - Group 2: numbers without this bit set Because x and y differ at this bit, they fall into different groups.

Result

Two groups where each unique number is isolated in separate groups.

Knowing that differing bits can separate unique numbers allows us to isolate them by grouping.

5

Intermediate

XOR Each Group to Find Unique Numbers

🤔Before reading on: Will XORing each group give one unique number or multiple? Commit to your answer.

Concept: XOR all numbers in each group to find the unique numbers separately.

Within each group, duplicates appear twice and cancel out. XORing all numbers in a group leaves the unique number in that group. Thus, XORing Group 1 gives one unique number, XORing Group 2 gives the other.

Result

Two unique numbers found without extra space or sorting.

Understanding that grouping based on differing bits isolates unique numbers for direct XOR extraction.

6

Advanced

Java Implementation with Step-by-Step Comments

🤔Before reading on: Predict the output of the code for input [2, 3, 7, 9, 2, 3]. Commit to your answer.

Concept: Implement the XOR approach in Java with clear comments explaining each step.

public class TwoUniqueNumbers { public static void findTwoUnique(int[] arr) { int xor = 0; // Step 1: XOR all elements for (int num : arr) { xor ^= num; } // Step 2: Find rightmost set bit int setBit = xor & (-xor); int num1 = 0, num2 = 0; // Step 3: Divide elements into two groups and XOR separately for (int num : arr) { if ((num & setBit) != 0) { num1 ^= num; } else { num2 ^= num; } } // Step 4: Print the two unique numbers System.out.println(num1 + " " + num2); } public static void main(String[] args) { int[] arr = {2, 3, 7, 9, 2, 3}; findTwoUnique(arr); } }

Result

7 9

Seeing the full code with comments clarifies how each XOR step isolates the unique numbers.

7

Expert

Why Rightmost Set Bit and Negative Number Trick Works

🤔Before reading on: Do you think using -xor to find the rightmost set bit is a trick or a fundamental property? Commit to your answer.

Concept: Understand the bitwise trick to isolate the rightmost set bit using negative numbers.

In two's complement, -xor is the bitwise complement of xor plus one. When we do xor & (-xor), it isolates the rightmost set bit because all bits except the rightmost set bit become zero. This is a fast way to find a mask for splitting numbers. This trick is widely used in bit manipulation problems for efficiency.

Result

Efficient mask to separate numbers based on differing bits.

Knowing this bitwise trick unlocks many advanced bit manipulation techniques beyond this problem.

Under the Hood

The XOR operation works at the bit level, comparing each bit of two numbers. When XORing all elements, pairs cancel out because identical bits XOR to zero. The remaining XOR result represents bits where the two unique numbers differ. Using the rightmost set bit of this result as a mask, the array is partitioned into two groups. Each group contains one unique number and pairs of duplicates. XORing each group cancels duplicates, leaving the unique number. This process uses bitwise arithmetic and properties of two's complement representation for negative numbers.

Why designed this way?

This method was designed to solve the problem in linear time and constant space, avoiding sorting or extra data structures. The XOR operation's properties naturally cancel duplicates, making it ideal. The rightmost set bit trick leverages two's complement arithmetic for efficient bit isolation. Alternatives like hash maps use extra space, and sorting changes order and costs more time. This approach balances speed and memory perfectly for this problem.

Input Array
  │
  ▼
XOR all elements
  │
  ▼
Combined XOR (x XOR y)
  │
  ▼
Find rightmost set bit (mask)
  │
  ▼
Split array into two groups based on mask bit
  │               │
  ▼               ▼
Group 1          Group 2
  │               │
XOR all elements XOR all elements
  │               │
  ▼               ▼
Unique x         Unique y

Myth Busters - 3 Common Misconceptions

Quick: Does XORing all elements give you one unique number or two? Commit to your answer.

Common Belief: XORing all elements will directly give the two unique numbers separately.

Reality: XORing all elements gives the XOR of the two unique numbers combined, not the numbers themselves.

Why it matters: Believing this leads to confusion and incorrect attempts to extract both numbers directly from the combined XOR.

Quick: Is the rightmost set bit always the best choice to split numbers? Commit to yes or no.

Common Belief: Any set bit in the combined XOR can be used to split the numbers equally well.

Reality: While any set bit can work, the rightmost set bit is chosen for simplicity and efficiency in implementation.

Why it matters: Choosing other bits complicates the code unnecessarily and may confuse learners.

Quick: Can this method find unique numbers if more than two numbers are unique? Commit to yes or no.

Common Belief: This XOR method works for any number of unique elements in the array.

Reality: This method only works when exactly two numbers are unique; it fails with more unique numbers.

Why it matters: Using this method incorrectly on other cases leads to wrong results and wasted debugging time.

Expert Zone

1

The order of the two unique numbers in output depends on which group they fall into; this is non-deterministic but usually acceptable.

2

Using xor & (-xor) exploits two's complement representation, which is a subtle but powerful trick in bit manipulation.

3

This approach can be extended to find one unique number among duplicates or adapted with more complex bit tricks for other problems.

When NOT to use

Avoid this method if there are more than two unique numbers or if duplicates do not appear exactly twice. In such cases, use hash maps or sorting-based methods.

Production Patterns

This XOR technique is used in embedded systems and performance-critical applications where memory is limited. It also appears in coding interviews to test bit manipulation skills and in error detection algorithms.

Connections

Bitwise XOR Operation

Builds-on

Mastering XOR is essential to understand how duplicates cancel out and unique elements remain, forming the core of this problem.

Two's Complement Number System

Underlying principle

Understanding two's complement explains why xor & (-xor) isolates the rightmost set bit, a key step in the solution.

Error Detection in Communication Systems

Similar pattern

XOR is used in parity checks and error detection codes, showing how this simple operation helps identify differences and errors in data.

Common Pitfalls

#1 Trying to find unique numbers by sorting and scanning without XOR.

Wrong approach:

Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
if (arr[i] != arr[i+1]) {
System.out.println(arr[i]);
}
}

Correct approach:

Use XOR method to find unique numbers efficiently without sorting.

Root cause:

Misunderstanding that sorting is necessary or efficient for this problem.

#2 Using xor & xor-1 to find rightmost set bit instead of xor & -xor.

Wrong approach:

int setBit = xor & (xor - 1);

Correct approach:

int setBit = xor & (-xor);

Root cause:

Confusing different bitwise tricks; xor & (xor-1) clears the rightmost set bit, not isolates it.

#3 Assuming the two unique numbers are always positive and ignoring sign bits.

Wrong approach:

if ((num & setBit) == 1) { ... } // wrong because setBit may not be 1

Correct approach:

if ((num & setBit) != 0) { ... } // correct check for set bit

Root cause:

Misunderstanding bitwise checks and assuming set bits equal 1 instead of non-zero.

Key Takeaways

XOR operation cancels out duplicate numbers, leaving combined XOR of unique numbers.

Finding the rightmost set bit in combined XOR helps split numbers into two groups to isolate unique elements.

XORing each group separately reveals the two unique numbers without extra memory or sorting.

The trick xor & (-xor) efficiently isolates the rightmost set bit using two's complement arithmetic.

This method only works when exactly two numbers are unique and all others appear twice.

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