Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template< class T > using Type_ = T;
- [[noreturn]] void noreturn() {}
- //-----------------------------------------------------------------------------
- #include <assert.h> // assert
- #include <iterator> // std::(begin, end, size)
- using std::begin, std::end, std::size;
- auto first_missing_in( const Type_<int*> values, const int n_values )
- -> int
- {
- assert( n_values > 0 );
- for( int i = 0; i < n_values; ++i ) {
- int j = i;
- int value = values[i];
- while( 1 <= value and value <= n_values and value - 1 != j ) {
- const int next_j = value - 1;
- const int next_value = values[next_j];
- values[next_j] = value;
- j = next_j; value = next_value;
- }
- }
- for( int i = 0; true; ++i ) {
- if( values[i] != i + 1 ) {
- return i + 1;
- }
- }
- }
- template< class Container >
- auto first_missing_in( Container& c )
- -> int
- { return first_missing_in( &*begin( c ), int( size( c ) ) ); }
- //-----------------------------------------------------------------------------
- #include <iomanip> // std::setw
- #include <iostream> // std::(cout, clog, endl)
- #include <sstream> // std::ostringstream
- using std::setw,
- std::cout, std::clog, std::endl,
- std::ostringstream;
- template< class Container >
- void show_example( Container& values )
- {
- ostringstream s;
- { // Make comma-separated list of the values.
- s << "[";
- for( const int& v: values ) {
- if( &v != &*values.begin() ) { s << ", "; }
- s << v;
- }
- s << "]";
- }
- const int m = first_missing_in( values );
- cout << setw( 20 ) << s.str() << " is missing " << m << "." << endl;
- }
- template< class Container >
- void show_example( Container&& values ) { show_example( values ); }
- //-----------------------------------------------------------------------------
- #include <array> // std::array
- #include <algorithm> // std::(sort, unique)
- #include <functional> // std::invoke
- #include <random> // std::*
- using std::array,
- std::sort, std::unique,
- std::invoke,
- std::default_random_engine, std::uniform_int_distribution;
- auto test( const int seed = 39 )
- -> bool
- {
- static constexpr int n = 1234;
- default_random_engine bits( seed );
- uniform_int_distribution<int> rnd_numbers( -n/4, n - 1 );
- array<int, n> data;
- for( int& item: data ) {
- item = rnd_numbers( bits );
- }
- const int fast_result = invoke( [&data]() -> int
- {
- array<int, n> a = data;
- return first_missing_in( a );
- } );
- const int correct_result = invoke( [&data]() -> int
- {
- array<int, n> a = data;
- sort( begin( a ), end( a ) );
- clog << "\n";
- for( const int value: a ) { clog << value << " "; }
- clog << "\n";
- const auto beyond = unique( begin( a ), end( a ) );
- const auto it_first_positive = find_if(
- begin( a ), beyond, []( int x ) { return x > 0; }
- );
- if( it_first_positive == end( a ) ) {
- return 1;
- }
- const int i_start = int( it_first_positive - begin( a ) );
- const int n_unique = int( beyond - begin( a ) );
- for( int i = i_start; i < n_unique; ++i ) {
- const int expected = 1 + (i - i_start);
- if( a[i] != expected ) {
- return expected;
- }
- }
- assert( false ); noreturn();
- } );
- clog << "Fast = " << fast_result << ", correct = " << correct_result << ".\n";
- return (fast_result == correct_result);
- }
- //-----------------------------------------------------------------------------
- #include <stdlib.h> // EXIT_...
- auto main()
- -> int
- {
- show_example( array{ 3, 4, -1, 1 } );
- show_example( array{ 1, 2, 0 } );
- const bool ok = test();
- cout << endl;
- cout << "Test " << (ok? "OK" : "FAILURE") << "." << endl;
- return (ok? EXIT_SUCCESS : EXIT_FAILURE);
- }
Add Comment
Please, Sign In to add comment