/// 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;
}

works