Given an array where every element appears twice except two elements that appear only once, find those two unique numbers.

Approach 1: Frequency Counting with Index Mapping

This method uses a temporary array to count occurrences by treating the original values as indices in the counting array.

#include <stdio.h>

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 6 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int count[100] = { 0 };

    for (int i = 0; i < len; i++) {
        if (count[arr[i]] == 0) {
            count[arr[i]] = 1;
        } else if (count[arr[i]] == 1) {
            count[arr[i]] = 2;
        }
    }

    for (int j = 0; j < 100; j++) {
        if (count[j] == 1) {
            printf("%d ", j);
        }
    }
    printf("\n");
    return 0;
}

How it works:

• A count array of size 100 (assuming values are within this range) is initialized to zero.
• For each element in the original array, the element itself is used as an index in count.
• If count[arr[i]] is 0, it means the number hasn't been seen before; set it to 1.
• If its already 1, set it to 2, indicating the number has appeared twice.
• Finally, scan the count array and print indices where the value is 1, because those correspond to numbers appearing exactly once.

Limitation: This approach assumes the original values are non-negative and fit within the index range of the counting array (here 0..99).

Approach 2: XOR Partitioning

This method leverages the XOR operation to separate the two unique numbers without extra space (except variables).

#include <stdio.h>

void findUnique(int arr[], int len, int* first, int* second) {
    int xorAll = 0;
    for (int i = 0; i < len; i++) {
        xorAll ^= arr[i];
    }

    // Find any set bit in xorAll, which differentiates the two unique numbers
    int rightmostBit = 1;
    while (!(xorAll & rightmostBit)) {
        rightmostBit <<= 1;
    }

    *first = 0;
    *second = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] & rightmostBit) {
            *first ^= arr[i];
        } else {
            *second ^= arr[i];
        }
    }
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 6 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int first = 0, second = 0;

    findUnique(arr, len, &first, &second);
    printf("%d %d\n", first, second);

    return 0;
}

How it works:

1. XOR all elements together. Pairs cancel out, leaving unique1 ^ unique2.
2. Find any bit that is set in the result (meaning the two unique numbers differ at that bit). The algorithm extracts the rightmost set bit.
3. Partition the array into two groups based on that bit. Since duplicates always go to the same group, XORing within each group yields one of the unique numbers.

Both methods output 5 and 6 for the example array.