Skip to content

Instantly share code, notes, and snippets.

@peschkaj
Last active Apr 16, 2018
Embed
What would you like to do?
Finds the missing element in an array using xor
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
//#define DEBUG
#define POWER 8
#define MAX 256
void shuffle(int* array, size_t n) {
if (n > 1) {
size_t i;
for (i = n - 1; i > 0; i--) {
size_t j = (unsigned int)arc4random_uniform(i + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
}
void print_array(int* array, size_t n, const char* message) {
unsigned int i;
printf("\n%s:\n", message);
for (i = 0; i < n; ++i) {
printf("%d ", array[i]);
}
printf("\n\n");
}
int main() {
int i, xor_result, missing;
int* array = malloc((sizeof(int) * MAX) - 1);
int sum = (MAX * (MAX + 1)) / 2;
int pos;
struct timeval tv;
gettimeofday(&tv, NULL);
int usec = tv.tv_usec;
srand48(usec);
missing = arc4random_uniform((unsigned int)MAX);
printf("missing number is %d\n", missing);
xor_result = MAX;
pos = 0;
// initialize array
for (i = 1; i <= MAX; ++i) {
if (i == missing) {
continue;
}
array[pos] = i;
++pos;
}
#ifdef DEBUG
print_array(array, MAX, "original array");
#endif
shuffle(array, MAX);
#ifdef DEBUG
print_array(array, MAX, "shuffled array");
#endif
for (i = 0; i < MAX; ++i) {
xor_result = xor_result ^ array[i];
}
printf("sum: %d\n", sum);
printf("xor_result: %d\n", xor_result);
free(array);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment