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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based two unique elements finder

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

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void findTwoUnique(const vector<int>& arr) {
    int xor_all = 0;
    for (int num : arr) {
        xor_all ^= num;
    }
    int set_bit = xor_all & (-xor_all);
    int x = 0, y = 0;
    for (int num : arr) {
        if (num & set_bit)
            x ^= num;
        else
            y ^= num;
    }
    cout << x << " " << y << endl;
}

int main() {
    vector<int> arr = {2, 3, 7, 9, 2, 3};
    findTwoUnique(arr);
    return 0;
}

A 7 9

B 2 3

C 9 7

D 0 0

💡 Hint

Focus on how XOR groups elements based on the rightmost set bit.

The code first XORs all elements to get xor_all = 7 ^ 9. Then it finds the rightmost set bit to separate elements into two groups. XORing each group gives the two unique numbers 7 and 9. The order is determined by which group is processed first, here 7 then 9.

🧠 Conceptual

intermediate

Why XOR helps find two unique elements?

Why does XOR operation help in finding two non-repeating elements in an array where all other elements repeat twice?

A Because XOR of two identical numbers is zero, so duplicates cancel out leaving XOR of unique elements

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

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

D Because XOR multiplies all elements and unique elements have different product

💡 Hint

Think about what happens when you XOR a number with itself.

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

🔧 Debug

advanced

Identify the error in this XOR-based two unique elements code

What error does the following code produce when trying to find two unique elements using XOR?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void findTwoUnique(const vector<int>& arr) {
    int xor_all = 0;
    for (int num : arr) {
        xor_all ^= num;
    }
    int set_bit = xor_all & (xor_all - 1);
    int x = 0, y = 0;
    for (int num : arr) {
        if (num & set_bit)
            x ^= num;
        else
            y ^= num;
    }
    cout << x << " " << y << endl;
}

int main() {
    vector<int> arr = {4, 1, 2, 1, 2, 5};
    findTwoUnique(arr);
    return 0;
}

A Compilation error due to invalid operator

B Outputs incorrect unique elements

C Runtime error due to division by zero

D Outputs zero zero

💡 Hint

Check how set_bit is calculated and what it represents.

The code uses 'xor_all & (xor_all - 1)' which clears the rightmost set bit instead of isolating it. This causes incorrect grouping and wrong output.

🚀 Application

advanced

Number of steps to find two unique elements using XOR

Given an array of size n with exactly two unique elements and all others repeated twice, how many XOR operations are performed in the standard XOR-based approach?

A 2n + 2

B n + 2

C 2n

D 3n

💡 Hint

Count XORs in the first loop and the second loop separately.

First loop XORs all n elements once (n XORs). Second loop XORs all n elements again to separate groups (n XORs). Total XORs = 2n.

❓ Predict Output

expert

Output of XOR-based two unique elements finder with negative numbers

What is the output of this C++ code that finds two unique elements in an array containing negative numbers using XOR?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void findTwoUnique(const vector<int>& arr) {
    int xor_all = 0;
    for (int num : arr) {
        xor_all ^= num;
    }
    int set_bit = xor_all & (-xor_all);
    int x = 0, y = 0;
    for (int num : arr) {
        if (num & set_bit)
            x ^= num;
        else
            y ^= num;
    }
    cout << x << " " << y << endl;
}

int main() {
    vector<int> arr = {-1, -2, -1, -3, -2, -4};
    findTwoUnique(arr);
    return 0;
}

A 0 0

B -4 -3

C -1 -2

D -3 -4

💡 Hint

Negative numbers work the same with XOR; focus on the rightmost set bit.

The XOR of all elements isolates the XOR of -3 and -4. The rightmost set bit separates them correctly, resulting in output '-3 -4'.

Practice

1. What is the main idea behind using XOR to find two non-repeating elements in an array where every other element repeats?

easy

A. XOR counts the frequency of each element

B. XOR sorts the array to separate unique elements

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

D. XOR swaps the two unique elements in the array

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself.

2. Step 2: Apply XOR to all elements

   XORing all elements cancels out repeating elements, leaving XOR of two unique elements.

3. Final Answer:

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

4. Quick Check:

   XOR cancels duplicates, leaving unique pair XOR [OK]

Hint: XOR all elements to isolate unique pair XOR result [OK]

Common Mistakes:

• Thinking XOR sorts or counts elements
• Assuming XOR gives unique elements directly
• Confusing XOR with addition or subtraction

2. Which of the following C++ code snippets correctly initializes the XOR variable to find two unique elements in an array arr of size n?

easy

A. int xorVal = 0; for(int i = 1; i <= n; i++) xorVal ^= arr[i];

B. int xorVal = 0; for(int i = 0; i < n; i++) xorVal ^= arr[i];

C. int xorVal = 1; for(int i = 0; i < n; i++) xorVal ^= arr[i];

D. int xorVal = arr[0]; for(int i = 1; i < n; i++) xorVal += arr[i];

Solution

1. Step 1: Initialize XOR with 0

   Start with 0 because XOR with 0 returns the number itself.

2. Step 2: Loop through array correctly

   Loop from 0 to n-1 to cover all elements; use XOR assignment operator ^=.

3. Final Answer:

   int xorVal = 0; for(int i = 0; i < n; i++) xorVal ^= arr[i]; -> Option B

4. Quick Check:

   Correct loop and XOR initialization [OK]

Hint: Initialize XOR with 0 and loop from 0 to n-1 [OK]

Common Mistakes:

• Starting loop from 1 and missing first element
• Using addition instead of XOR
• Initializing XOR with 1 instead of 0
• Looping out of array bounds

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

int arr[] = {2, 3, 7, 9, 2, 3};
int n = 6;
int xorVal = 0;
for(int i = 0; i < n; i++) {
    xorVal ^= arr[i];
}
std::cout << xorVal << std::endl;

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result is XOR of two unique elements

   Since 2 and 3 repeat, XOR leaves 7 and 9 combined as 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR of unique pair (7^9) = 14 [OK]

Hint: XOR duplicates cancel; result is XOR of unique elements [OK]

Common Mistakes:

• Calculating XOR incorrectly stepwise
• Assuming output is one unique element
• Confusing XOR with sum

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

int xorVal = 0;
for(int i = 0; i <= n; i++) {
    xorVal ^= arr[i];
}

medium

A. Loop runs out of array bounds causing runtime error

B. XOR operator is used incorrectly

C. xorVal should be initialized with arr[0]

D. Loop should start from 1 instead of 0

Solution

1. Step 1: Check loop bounds

   Loop runs from i=0 to i<=n, which means i goes up to n, exceeding array index (0 to n-1).

2. Step 2: Consequence of out-of-bounds access

   Accessing arr[n] causes undefined behavior or runtime error.

3. Final Answer:

   Loop runs out of array bounds causing runtime error -> Option A

4. Quick Check:

   Array index must be less than n [OK]

Hint: Use i < n in loops to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing xorVal incorrectly
• Starting loop from wrong index

5. Given the array arr = {4, 1, 2, 1, 2, 5}, which of the following steps correctly finds the two non-repeating elements using XOR?

hard

A. Add all elements and subtract twice the sum of repeating elements

B. Sort array, then pick first two elements as unique

C. XOR all elements to get 1, then XOR with 0 to get unique elements

D. XOR all elements to get 1, find rightmost set bit, partition array by this bit, XOR partitions separately

Solution

1. Step 1: XOR all elements

   XOR(4^1^2^1^2^5) = 4 ^ (1^1) ^ (2^2) ^ 5 = 4 ^ 0 ^ 0 ^ 5 = 1.

2. Step 2: Find rightmost set bit of XOR result

   Rightmost set bit of 1 is 1 (binary 0001).

3. Step 3: Partition array by this bit and XOR separately

   Group elements with this bit set and not set, XOR each group to find unique elements 4 and 5.

4. Final Answer:

   XOR all elements to get 1, find rightmost set bit, partition array by this bit, XOR partitions separately -> Option D

5. Quick Check:

   Partitioning by set bit isolates unique elements [OK]

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

Common Mistakes:

• Skipping partition step after XOR
• Using sorting instead of XOR
• Confusing addition with XOR