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 <stdio.h>

void findTwoUnique(int arr[], int n) {
    int xor = 0;
    for (int i = 0; i < n; i++) {
        xor ^= arr[i];
    }
    int set_bit = xor & ~(xor - 1);
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit)
            x ^= arr[i];
        else
            y ^= arr[i];
    }
    printf("%d %d\n", x, y);
}

int main() {
    int arr[] = {2, 3, 7, 9, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTwoUnique(arr, n);
    return 0;
}

A 7 9

B 9 7

C 2 3

D 0 0

💡 Hint

Focus on how XOR and set bits separate the two unique numbers.

The XOR of all elements gives xor = 14 (binary 1110). The rightmost set bit is 2 (binary 0010). Splitting elements by this bit separates 7 and 9. XORing each group gives 7 and 9. The order printed is x then y, which is 7 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 every other element repeats twice?

A XOR adds all numbers to find the sum of unique elements

B XOR multiplies all numbers to find product of unique elements

C XOR sorts the array to separate unique elements

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

💡 Hint

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

XOR of a number with itself is zero, so all duplicates cancel out. The result is XOR of the two unique elements, which helps to separate them.

❓ Predict Output

advanced

Output of modified XOR code with different array

What is the output of this C code that finds two unique elements using XOR?

DSA C

#include <stdio.h>

void findTwoUnique(int arr[], int n) {
    int xor = 0;
    for (int i = 0; i < n; i++) {
        xor ^= arr[i];
    }
    int set_bit = xor & ~(xor - 1);
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit)
            x ^= arr[i];
        else
            y ^= arr[i];
    }
    printf("%d %d\n", x, y);
}

int main() {
    int arr[] = {4, 1, 2, 1, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTwoUnique(arr, n);
    return 0;
}

A 0 0

B 4 5

C 5 4

D 1 2

💡 Hint

Check which bit is set in XOR and how elements split.

XOR of all elements is 1 (binary 0001). The rightmost set bit is 1. Splitting elements by this bit separates 5 and 4. XORing each group gives 5 and 4. The code prints x then y, which is 5 4.

🔧 Debug

advanced

Identify the error in XOR two unique elements code

What error will this code produce when finding two unique elements using XOR?

DSA C

#include <stdio.h>

void findTwoUnique(int arr[], int n) {
    int xor = 0;
    for (int i = 0; i <= n; i++) {
        xor ^= arr[i];
    }
    int set_bit = xor & ~(xor - 1);
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit)
            x ^= arr[i];
        else
            y ^= arr[i];
    }
    printf("%d %d\n", x, y);
}

int main() {
    int arr[] = {2, 3, 7, 9, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTwoUnique(arr, n);
    return 0;
}

A Compilation error due to missing semicolon

B Segmentation fault due to out-of-bounds array access

C Logical error printing wrong unique elements

D No error, prints correct output

💡 Hint

Check the loop boundary in the first for loop.

The loop runs from i = 0 to i <= n, which accesses arr[n], out of bounds causing segmentation fault.

🚀 Application

expert

Number of items in result after XOR partition

Given an array where all elements except two appear twice, after XORing all elements and splitting by rightmost set bit, how many elements will be in each partition?

A One partition has all duplicates plus one unique element; the other has the other unique element only

B Both partitions have equal number of elements

C One partition has only duplicates; the other has both unique elements

D Both partitions have only unique elements

💡 Hint

Duplicates appear twice and share bits; unique elements differ in the chosen bit.

Duplicates appear twice and fall into the same partition, so one partition has all duplicates plus one unique element, the other partition has the other unique element only.