Skip to content

Instantly share code, notes, and snippets.

@mfukar
Created May 13, 2015 09:54
Show Gist options
  • Save mfukar/10cd3e02379da1778249 to your computer and use it in GitHub Desktop.
Save mfukar/10cd3e02379da1778249 to your computer and use it in GitHub Desktop.
Just some random interview question + solution, I don't even remember from where any more
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment