Find next greater element with no consecutive 1 in it 's binary representation | Java 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
import java . io . * ; import java . util . * ; class GFG { static int MAX = 100000 ; static ArrayList < Integer > v = new ArrayList < Integer > ( ) ; public static int upper_bound ( ArrayList < Integer > ar , int k ) { int s = 0 ; int e = ar . size ( ) ; while ( s != e ) { int mid = s + e >> 1 ; if ( ar . get ( mid ) <= k ) { s = mid + 1 ; } else { e = mid ; } } if ( s == ar . size ( ) ) { 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 . get ( it ) ; return val ; } static void performQueries ( int queries [ ] , int q ) { for ( int i = 0 ; i < q ; i ++ ) { System . out . println ( nextValid ( queries [ i ] ) ) ; } } public static void main ( String [ ] args ) { int queries [ ] = { 4 , 6 } ; int q = queries . length ; preCompute ( ) ; performQueries ( queries , q ) ; } }