alfps

First missing positive number

May 29th, 2020
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.14 KB | None | 0 0
  1. template< class T > using Type_ = T;
  2. [[noreturn]] void noreturn() {}
  3.  
  4.  
  5. //-----------------------------------------------------------------------------
  6. #include <assert.h>         // assert
  7. #include <iterator>         // std::(begin, end, size)
  8. using   std::begin, std::end, std::size;
  9.  
  10. auto first_missing_in( const Type_<int*> values, const int n_values )
  11.     -> int
  12. {
  13.     assert( n_values > 0 );
  14.     for( int i = 0; i < n_values; ++i ) {
  15.         int j = i;
  16.         int value = values[i];
  17.         while( 1 <= value and value <= n_values and value - 1 != j ) {
  18.             const int next_j = value - 1;
  19.             const int next_value = values[next_j];
  20.             values[next_j] = value;
  21.            
  22.             j = next_j;  value = next_value;
  23.         }
  24.     }
  25.  
  26.     for( int i = 0; true; ++i ) {
  27.         if( values[i] != i + 1 ) {
  28.             return i + 1;
  29.         }
  30.     }
  31. }
  32.  
  33. template< class Container >
  34. auto first_missing_in( Container& c )
  35.     -> int
  36. { return first_missing_in( &*begin( c ), int( size( c ) ) ); }
  37.  
  38.  
  39. //-----------------------------------------------------------------------------
  40. #include <iomanip>          // std::setw
  41. #include <iostream>         // std::(cout, clog, endl)
  42. #include <sstream>          // std::ostringstream
  43. using   std::setw,
  44.         std::cout, std::clog, std::endl,
  45.         std::ostringstream;
  46.  
  47. template< class Container >
  48. void show_example( Container& values )
  49. {
  50.     ostringstream s;
  51.     { // Make comma-separated list of the values.
  52.         s << "[";
  53.         for( const int& v: values ) {
  54.             if( &v != &*values.begin() ) { s << ", "; }
  55.             s << v;
  56.         }
  57.         s << "]";
  58.     }
  59.     const int m = first_missing_in( values );
  60.     cout << setw( 20 ) << s.str() << " is missing " << m << "." << endl;
  61. }
  62.  
  63. template< class Container >
  64. void show_example( Container&& values ) { show_example( values ); }
  65.  
  66.  
  67. //-----------------------------------------------------------------------------
  68. #include <array>            // std::array    
  69. #include <algorithm>        // std::(sort, unique)
  70. #include <functional>       // std::invoke    
  71. #include <random>           // std::*
  72. using   std::array,
  73.         std::sort, std::unique,
  74.         std::invoke,
  75.         std::default_random_engine, std::uniform_int_distribution;
  76.  
  77. auto test( const int seed = 39 )
  78.     -> bool
  79. {
  80.     static constexpr int n = 1234;
  81.     default_random_engine bits( seed );
  82.     uniform_int_distribution<int> rnd_numbers( -n/4, n - 1 );
  83.    
  84.     array<int, n> data;
  85.     for( int& item: data ) {
  86.         item = rnd_numbers( bits );
  87.         }
  88.  
  89.     const int fast_result = invoke( [&data]() -> int
  90.     {
  91.         array<int, n> a = data;
  92.         return first_missing_in( a );
  93.     } );
  94.    
  95.     const int correct_result = invoke( [&data]() -> int
  96.     {
  97.         array<int, n> a = data;
  98.         sort( begin( a ), end( a ) );
  99.  
  100.         clog << "\n";
  101.         for( const int value: a ) { clog << value << " "; }
  102.         clog << "\n";
  103.  
  104.         const auto beyond = unique( begin( a ), end( a ) );
  105.        
  106.         const auto it_first_positive = find_if(
  107.             begin( a ), beyond, []( int x ) { return x > 0; }
  108.             );
  109.  
  110.         if( it_first_positive == end( a ) ) {
  111.             return 1;
  112.         }
  113.         const int i_start = int( it_first_positive - begin( a ) );
  114.         const int n_unique = int( beyond - begin( a ) );
  115.         for( int i = i_start; i < n_unique; ++i ) {
  116.             const int expected = 1 + (i - i_start);
  117.             if( a[i] != expected ) {
  118.                 return expected;
  119.             }
  120.         }
  121.         assert( false );  noreturn();
  122.     } );
  123.    
  124.     clog << "Fast = " << fast_result << ", correct = " << correct_result << ".\n";
  125.     return (fast_result == correct_result);
  126. }
  127.  
  128.  
  129. //-----------------------------------------------------------------------------
  130. #include <stdlib.h>     // EXIT_...
  131.  
  132. auto main()
  133.     -> int
  134. {
  135.     show_example( array{ 3, 4, -1, 1 } );
  136.     show_example( array{ 1, 2, 0 } );
  137.    
  138.     const bool ok = test();
  139.     cout << endl;
  140.     cout << "Test " << (ok? "OK" : "FAILURE") << "." << endl;
  141.     return (ok? EXIT_SUCCESS : EXIT_FAILURE);
  142. }
Add Comment
Please, Sign In to add comment