/// Write a function to find the missing number in a list
/// @param[in] arr Input array
/// @param[in] size Size of array
/// All elements in array are unique and in range 1 to size + 1
/// @ret Missing number
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int xorer_(int a, int b) {
return a ^ b;
}
int findMissing(int *arr, int size) {
const int expectedArray[] = {1, size + 2, 0, size + 1};
const int expected = expectedArray[size % 4];
return accumulate(arr, arr+size, expected, xorer_);
}
void test() {
const int size = 5000;
int arr[size+1] = {0};
for(int i = 0; i <= size; ++i) arr[i] = i+1;
random_shuffle(arr, arr+size+1);
const int &expected = arr[size];
const int funresult = findMissing(arr, size);
if(expected != funresult) cout << "Expected: " << expected << ", actual: " << funresult << endl;
else cout << "works" << endl;
}
int main() {
srand(0);
for(int i = 0; i < 10; ++i) test();
return 0;
}