Just some random interview question + solution, I don't even remember from where any more

idontknow.c

/**
 * The array contains a set of unsorted numbers. All numbers appear an even number of
 * times. The exception is two numbers, call them M and N, which appear an odd number of
 * times.  Find M and N.
 *
 * This solution is O(n), where n is the size of the array. It requires two passes over
 * the array.
 *
 * The generalised version of this problem (N elements, one number repeats K times) can
 * be reduced to solving the linear system of equations:
 * Sp(x1, ..., xN) = Σ from K=1 to N of xK to the power of p
 *
 * PROOF for K=2: Let y be the repeating and x the missing element. Calculate the sum and
 * the square sum. We know:
 *       sum = n * (n+1) / 2 - y + x
 *     sqsum = n * (n+1) * (2*n+1) /  6 - x^2 + y^2
 * We can now solve for x & y.
 * Exercise for the reader: Generalise to K by induction.
 *
 */
#include <stdio.h>

#define BIT_CHECK(number, b) ((number) & (1 << (b)))

int main()
{
    int array[] = { 5, 14, 3, 2, 7, 6, 6, 7, 7, 7, 1, 8, 8, 5, 3, 2, 4, 4, 1, 1};
    int x = 0, m = 0, n = 0;

    for (size_t index = 0; index < sizeof array / sizeof *array; ++index) {
        x ^= array[index];
    }

    int pos = 0;
    while (BIT_CHECK(x, pos) == 0) {
        ++pos;
    }

    for (size_t index = 0; index < sizeof array / sizeof *array; ++index) {
        if (BIT_CHECK(array[index], pos) == 0) {
            m ^= array[index];
        } else {
            n ^= array[index];
        }
    }

    printf("M: %d  N: %d\n", m, n);
    return 0;
}