text: Find next greater element with no consecutive 1 in it 's binary representation | C ++ implementation of the approach ; To store the pre - computed integers ; Function that returns true if the binary representation of x contains consecutive 1 s ; To store the previous bit ; Check whether the previous bit and the current bit are both 1 ; Update previous bit ; Go to the next bit ; Function to pre - compute the valid numbers from 0 to MAX ; Store all the numbers which do not have consecutive 1 s ; Function to return the minimum number greater than n which does not contain consecutive 1 s ; Search for the next greater element with no consecutive 1 s ; Function to perform the queries ; Driver code ; Pre - compute the numbers ; Perform the queries
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 100000 ; vector < int > v ; int consecutiveOnes ( int x ) { int p = 0 ; while ( x > 0 ) { if ( x % 2 == 1 and p == 1 ) return true ; p = x % 2 ; x /= 2 ; } return false ; } void preCompute ( ) { for ( int i = 0 ; i <= MAX ; i ++ ) { if ( ! consecutiveOnes ( i ) ) v . push_back ( i ) ; } } int nextValid ( int n ) { int it = upper_bound ( v . begin ( ) , v . end ( ) , n ) - v . begin ( ) ; int val = v [ it ] ; return val ; } void performQueries ( int queries [ ] , int q ) { for ( int i = 0 ; i < q ; i ++ ) cout << nextValid ( queries [ i ] ) << " STRNEWLINE " ; } int main ( ) { int queries [ ] = { 4 , 6 } ; int q = sizeof ( queries ) / sizeof ( int ) ; preCompute ( ) ; performQueries ( queries , q ) ; return 0 ; }