Find next greater element with no consecutive 1 in it 's binary representation | Python3 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
from bisect import bisect_right as upper_bound NEW_LINE MAX = 100000 NEW_LINE v = [ ] NEW_LINE def consecutiveOnes ( x ) : NEW_LINE INDENT p = 0 NEW_LINE while ( x > 0 ) : NEW_LINE INDENT if ( x % 2 == 1 and p == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT p = x % 2 NEW_LINE x //= 2 NEW_LINE DEDENT return False NEW_LINE DEDENT def preCompute ( ) : NEW_LINE INDENT for i in range ( MAX + 1 ) : NEW_LINE INDENT if ( consecutiveOnes ( i ) == 0 ) : NEW_LINE INDENT v . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def nextValid ( n ) : NEW_LINE INDENT it = upper_bound ( v , n ) NEW_LINE val = v [ it ] NEW_LINE return val NEW_LINE DEDENT def performQueries ( queries , q ) : NEW_LINE INDENT for i in range ( q ) : NEW_LINE INDENT print ( nextValid ( queries [ i ] ) ) NEW_LINE DEDENT DEDENT queries = [ 4 , 6 ] NEW_LINE q = len ( queries ) NEW_LINE preCompute ( ) NEW_LINE performQueries ( queries , q ) NEW_LINE