/// 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 findMissing(int *arr, int size) {
int res = 0;
int i = 0;
while(i < size) {
// A loop free way would be to write a function that
// xor two integers and use numeric > accumulate to
// accumulate the numbers.
// Write another function that can output the acc(1, N)
res ^= arr[i++];
res ^= i;
}
return res ^ (i+1);
}
int main() {
const int size = 5000;
srand(0);
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;
return 0;
}