codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/// 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; }
Private
[
?
]
Run code
Submit