Two Non Repeating Elements in Array Using XOR in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based two non-repeating elements finder

What is the output of the following Java code that finds two non-repeating elements in an array using XOR?

DSA Java

public class Solution {
    public static void findTwoNonRepeating(int[] arr) {
        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 + " -> null");
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 7, 9, 2, 3};
        findTwoNonRepeating(arr);
    }
}

A 7 -> 9 -> null

B 9 -> 7 -> null

C 2 -> 3 -> null

D 3 -> 2 -> null

💡 Hint

Focus on how XOR helps isolate the two unique numbers and how the set bit divides the array.

The XOR of all elements gives xor = 7 ^ 9. The rightmost set bit in xor is used to separate numbers into two groups. XORing each group gives the two unique numbers 7 and 9. The order printed is 7 first then 9.

❓ Predict Output

intermediate

Output of XOR-based two non-repeating elements finder with different input

What is the output of the following Java code that finds two non-repeating elements in an array using XOR?

DSA Java

public class Solution {
    public static void findTwoNonRepeating(int[] arr) {
        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 + " -> null");
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 2, 1, 2, 5};
        findTwoNonRepeating(arr);
    }
}

A 4 -> 5 -> null

B 2 -> 1 -> null

C 1 -> 2 -> null

D 5 -> 4 -> null

💡 Hint

Check how the set bit divides the array into two groups and XOR each group.

The XOR of all elements is 4 ^ 5. The rightmost set bit separates numbers into two groups. XORing each group yields 5 and 4. The order printed is 5 then 4.

🔧 Debug

advanced

Identify the error in XOR two non-repeating elements code

What error does the following Java code produce when trying to find two non-repeating elements using XOR?

DSA Java

public class Solution {
    public static void findTwoNonRepeating(int[] arr) {
        int xor = 0;
        for (int num : arr) {
            xor ^= num;
        }
        int setBit = xor & (xor - 1);
        int x = 0, y = 0;
        for (int num : arr) {
            if ((num & setBit) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        System.out.println(x + " -> " + y + " -> null");
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 7, 9, 2, 3};
        findTwoNonRepeating(arr);
    }
}

A SyntaxError due to missing parentheses

B RuntimeException: division by zero

C Logical error: incorrect setBit calculation leads to wrong output

D No error, correct output

💡 Hint

Check how setBit is calculated using xor & -xor vs xor & xor-1.

The expression xor & xor-1 clears the rightmost set bit instead of isolating it. This causes incorrect grouping and wrong output.

🧠 Conceptual

advanced

Why XOR helps find two unique elements in array?

Why does XOR operation help in finding two non-repeating elements in an array where every other element repeats twice?

A Because XOR adds all numbers together to find sum of unique elements

B Because XOR of two same numbers is zero, so all repeating elements cancel out leaving XOR of unique elements

C Because XOR sorts the array and unique elements appear at ends

D Because XOR multiplies all numbers to find product of unique elements

💡 Hint

Recall properties of XOR with identical numbers.

XOR of a number with itself is zero, so pairs cancel out. XOR of all elements leaves XOR of two unique elements.

❓ Predict Output

expert

Output of XOR two non-repeating elements with negative numbers

What is the output of the following Java code that finds two non-repeating elements in an array containing negative numbers using XOR?

DSA Java

public class Solution {
    public static void findTwoNonRepeating(int[] arr) {
        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 + " -> null");
    }

    public static void main(String[] args) {
        int[] arr = {-1, -2, -1, -3, -2, -4};
        findTwoNonRepeating(arr);
    }
}

A -3 -> -4 -> null

B -2 -> -1 -> null

C -1 -> -2 -> null

D -4 -> -3 -> null

💡 Hint

XOR works the same with negative numbers; check the rightmost set bit carefully.

XOR of all elements isolates -3 and -4 as unique. The rightmost set bit divides them correctly. Output is '-3 -> -4 -> null'.

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