[ create a new paste ] login | about

Link: http://codepad.org/JnMTQD3O    [ raw code | output | fork ]

mohit_at_codepad - C++, pasted on Jun 20:
/// 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;
}


Output:
1
2
3
4
5
6
7
8
9
10
works
works
works
works
works
works
works
works
works
works


Create a new paste based on this one


Comments: