| #include "stdlib.h" | |
| #include "stdio.h" | |
| #define ARRAY_SIZE 500000 | |
| #define NLOOPS1 5 | |
| #define NLOOPS2 200 | |
| // RNG implemented localy to avoid library incongruences | |
| #ifdef RAND_MAX | |
| #undef RAND_MAX | |
| #endif | |
| #define RAND_MAX 32767 | |
| static unsigned long long int next = 1; | |
| int rand( void ) { | |
| next = next * 1103515245 + 12345; | |
| return (unsigned int)(next / 65536) % RAND_MAX+1; | |
| } | |
| void srand( unsigned int seed ) { | |
| next = seed; | |
| } | |
| // End of RNG implementation | |
| int randInt(int min, int max) { | |
| int k, n; | |
| n = (max - min) + 1; | |
| k = (int)(n * (rand() / (RAND_MAX + 1.0))); | |
| return (k == n) ? k + min - 1 : k + min; | |
| } | |
| void shuffle(int* items, int len) { | |
| size_t j, k, i; | |
| int aux; | |
| for(i = len-1; i > 0; --i) { | |
| k = (int)((i + 1) * (rand() / (RAND_MAX + 1.0))); | |
| j = (k == (i + 1)) ? k - 1 : k; | |
| aux = items[i]; | |
| items[i] = items[j]; | |
| items[j] = aux; | |
| } | |
| } | |
| int *createRandomArray(int size) { | |
| int i, len; | |
| int *result; | |
| len = size + 1; | |
| result = (int*)malloc(len * sizeof(int)); | |
| for (i = 0; i < len; i++) | |
| result[i] = i; | |
| result[0] = randInt(1, size); | |
| shuffle(result, len); | |
| return result; | |
| } | |
| int findDuplicate(int *data, int len) { | |
| int i; | |
| int result = 0; | |
| for (i = 0; i < len; i++) | |
| result = result ^ (i + 1) ^ data[i]; | |
| result ^= len; | |
| return result; | |
| } | |
| int main() { | |
| int i, j, duplicate; | |
| int *rndArr; | |
| srand(1); | |
| for (i = 0; i < NLOOPS1; i++) { | |
| rndArr = createRandomArray(ARRAY_SIZE); | |
| for (j = 0; j < NLOOPS2; j++) | |
| duplicate = findDuplicate(rndArr, ARRAY_SIZE+1); | |
| free(rndArr); | |
| printf("Found duplicate: %d\n", duplicate); | |
| } | |
| return 0; | |
| } |