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: using System ; using System . Collections . Generic ; class GFG { static int MAX = 100000 ; static List < int > v = new List < int > ( ) ; static int upper_bound ( List < int > ar , int k ) { int s = 0 ; int e = ar . Count ; while ( s != e ) { int mid = s + e >> 1 ; if ( ar [ mid ] <= k ) { s = mid + 1 ; } else { e = mid ; } } if ( s == ar . Count ) { return - 1 ; } return s ; } static int consecutiveOnes ( int x ) { int p = 0 ; while ( x > 0 ) { if ( x % 2 == 1 && p == 1 ) { return 1 ; } p = x % 2 ; x /= 2 ; } return 0 ; } static void preCompute ( ) { for ( int i = 0 ; i <= MAX ; i ++ ) { if ( consecutiveOnes ( i ) == 0 ) { v . Add ( i ) ; } } } static int nextValid ( int n ) { int it = upper_bound ( v , n ) ; int val = v [ it ] ; return val ; } static void performQueries ( int [ ] queries , int q ) { for ( int i = 0 ; i < q ; i ++ ) { Console . WriteLine ( nextValid ( queries [ i ] ) ) ; } } static public void Main ( ) { int [ ] queries = { 4 , 6 } ; int q = queries . Length ; preCompute ( ) ; performQueries ( queries , q ) ; } }