/* by Bell Including a cool header with iterator pairs by Chris Welshman Find it under: https://github.com/cwzx/lazy-iterators/blob/master/distinct_pairs.h explanation: https://cwzx.wordpress.com/2014/04/15/iterating-over-distinct-pairs-in-cpp/ Challenge by VcC Given a list L of n numbers positive or negative 1- Find if L contrains two numbers which sum is zero. If so print them. If not print false 2- Same for 3 numbers summing to zero ExL[1,2,3,-7,5,-6.5,10,-2,5,11] 1: [2,-2] 2: [5,1,-6] Try to make a fast code.... std::vector input_array {3, 12, -6, 27, 8, 18, -66, 47, 11}; // input example for(const std::pair & mp : magical_pairs(input_array)) std::cout << mp.first << " : " << mp.second << std::endl; -x == ~x + 1 // a big vector vector v( 1 << 17 ); // fill the vector with ascending numbers starting with 1 iota( begin(v), end(v), 1 ); // count the number of distinct pairs whose sum is even auto ps = distinct_pairs(v); cout << count_if( begin(ps), end(ps), []( auto p ) { return ( p.first + p.second ) % 2 == 0; } );*/ #include #include using namespace std; /* * Chris Welshman 2014 */ #ifndef INCLUDED_DISTINCT_PAIRS #define INCLUDED_DISTINCT_PAIRS #include #include template struct distinct_pairs_iterator { typedef typename std::iterator_traits::value_type original_value_type; typedef typename std::iterator_traits::reference original_reference; typedef typename std::iterator_traits::difference_type difference_type; typedef typename std::iterator_traits::iterator_category iterator_category; typedef std::pair value_type; typedef std::pair reference; typedef std::pair pair_type; typedef const pair_type* pointer; distinct_pairs_iterator() = default; explicit distinct_pairs_iterator( const pair_type& range ) : range(range) { pair.first = range.first; pair.second = range.first; if( range.first != range.second ) ++pair.second; } distinct_pairs_iterator( const Iterator& first, const Iterator& last ) : distinct_pairs_iterator(pair_type(first,last)) {} distinct_pairs_iterator( const pair_type& range, const pair_type& pair ) : range(range), pair(pair) {} reference operator*() const { return reference( *pair.first, *pair.second ); } pointer operator->() const { return &pair; } original_reference first() const { return *pair.first; } original_reference second() const { return *pair.second; } distinct_pairs_iterator& operator++() { ++pair.second; if( pair.second == range.second ) { ++pair.first; pair.second = pair.first; ++pair.second; } return *this; } distinct_pairs_iterator operator++(int) { distinct_pairs_iterator temp = *this; ++(*this); return temp; } distinct_pairs_iterator& operator--() { --pair.second; if( pair.second == pair.first ) { --pair.first; pair.second = range.second; --pair.second; } return *this; } distinct_pairs_iterator operator--(int) { distinct_pairs_iterator temp = *this; --(*this); return temp; } distinct_pairs_iterator& operator+=( difference_type offset ) { difference_type N = std::distance( range.first, range.second ); difference_type k = index(N) + offset; difference_type i = index_i( k, N ); difference_type j = index_j( k, i, N ); pair.first = range.first + i; pair.second = range.first + j; return *this; } distinct_pairs_iterator operator+( difference_type offset ) const { distinct_pairs_iterator temp = *this; return temp += offset; } distinct_pairs_iterator& operator-=( difference_type offset ) const { return *this += -offset; } distinct_pairs_iterator operator-( difference_type offset ) const { distinct_pairs_iterator temp = *this; return temp -= offset; } difference_type operator-( const distinct_pairs_iterator& rhs ) const { difference_type dfirst = std::distance( rhs.pair.first, pair.first ); difference_type dsecond = std::distance( rhs.pair.second, pair.second ); difference_type N = std::distance( range.first, range.second ); difference_type sumfirst = std::distance( range.first, pair.first ) + std::distance( range.first, rhs.pair.first ); return ( ( 2*(N-1) - 1 - sumfirst ) * dfirst ) / 2 + dsecond; } reference operator[]( difference_type offset ) const { return *(*this + offset); } difference_type index() const { difference_type N = std::distance( range.first, range.second ); return index(N); } bool operator==( const distinct_pairs_iterator& rhs ) const { if( pair == rhs.pair ) return true; if( pair.first == rhs.pair.second && pair.second == rhs.pair.first ) return true; return false; } bool operator!=( const distinct_pairs_iterator& rhs ) const { return !(*this == rhs); } bool operator<( const distinct_pairs_iterator& rhs ) const { return rhs - *this > 0; } bool operator>( const distinct_pairs_iterator& rhs ) const { return rhs < *this; } bool operator<=( const distinct_pairs_iterator& rhs ) const { return !( *this > rhs ); } bool operator>=( const distinct_pairs_iterator& rhs ) const { return !( *this < rhs ); } protected: pair_type range, pair; difference_type index( difference_type N ) const { return index( std::distance( range.first, pair.first ), std::distance( range.first, pair.second ), N ); } difference_type index( difference_type i, difference_type j, difference_type N ) const { return j - i + ( i * ( 2*N - ( i + 1 ) ) ) / 2 - 1; } difference_type index_i( difference_type k, difference_type N ) const { difference_type d = N, total = 0; for(difference_type a=0;a k ) return a; } return N-1; } difference_type index_j( difference_type k, difference_type i, difference_type N ) const { return (k + i + 1) - ( i * ( 2*N - ( i + 1 ) ) ) / 2; } }; template struct distinct_pairs_range { typedef typename std::iterator_traits::value_type value_type; typedef typename std::iterator_traits::difference_type difference_type; typedef Iterator original_iterator; typedef distinct_pairs_iterator iterator; typedef std::reverse_iterator reverse_iterator; typedef std::pair pair_type; explicit distinct_pairs_range( const pair_type& range ) : range(range) {} distinct_pairs_range( const Iterator& first, const Iterator& last ) : range(pair_type(first,last)) {} difference_type size() const { difference_type N = std::distance( range.first, range.second ); return ( N * ( N - 1 ) ) / 2; } iterator begin() const { return iterator( range ); } iterator end() const { pair_type temp = range; temp.first = range.second; if( range.first != range.second ) --temp.first; return iterator( range, temp ); } protected: pair_type range; }; template inline distinct_pairs_range distinct_pairs( Iterator&& first, Iterator&& last ) { return distinct_pairs_range( std::make_pair( std::forward(first), std::forward(last) ) ); } template inline auto distinct_pairs( Range&& r ) { return distinct_pairs( begin( std::forward(r) ), end( std::forward(r) ) ); } template inline auto cdistinct_pairs( const Range& r ) { return distinct_pairs( cbegin( r ), cend( r ) ); } #endif int main() { cout<<"Challenge from VcC, find groups of numbers adding to zero"< v {1,2,3,-7,5,-6,5,10,-2,5,11}; for( auto p : distinct_pairs(v) ) { if(( p.first + p.second ) == 0) cout << "( " << p.first << ", " << p.second << " )" << endl; } /*for( auto p : distinct_pairs(distinct_pairs(v))) { if(( p.first.first + p.first.second + p.second.second ) == 0) cout << "( " << p.first.first << ", " << p.first.second << ", " <

VcCPairChallenge